[백준]사다리 조작

https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

시간은 좀 걸리긴 했지만 비슷한듯 다른듯 하면서의 느낌의 문제다.

일단 dfs 재귀 + 시뮬레이션 의 문제이다. dfs재귀로 조합을 구하면 해결가능 한 문제였다.

시간초과가 발생했었는데, 중복순열로 계산되어서 시간초과가 발생했다.

이차원배열에 대해서 조합을 이용해 약간 특이했다.

해결하기 위해 조합을 사용했고, 행에 대해서만 쭉쭉 다음으로 넘겨주었더니 해결됬다.

열까지 해주었을때는, 대각선 아래로 탐색이 되어서 제대로 된 탐색이 이루어지지 않아서 오답이 나왔다.

시뮬레이션 부분에서는 처음에는 다리를 모두 1로 표시했더니 왼쪽오른쪽 구분을 하지못해서 에러가 나왔다.

그래서 세로번호로 주어서 다리숫자를 입력해주었고, 마지막행에 도달했을때 바로 종료해서 에러가 나왔다.

마지막행에서도 사다리를 탈 수 있었기때문에 고쳐주었다.

특이했던 점은, 최소사다리 개수를 구하는것이기 때문에 bfs를 생각해보았으나 3개의 사다리를 완전탐색으로 

맵에 놓아주기가 매우 어려워서 dfs로 돌려서 생각했다. 그리고 bool 타입을 이용해 종료를 할 수 있게 조작했다.

end를 for으로 돌려주면서 1~3개의 사다리를 for문으로 사용해주었다. 

 

#include <iostream>
#include <cstring>
using namespace std;
 
/*
1.완탐으로 사다리 개수를 1~3까지 해서 다 놓어보는 경우
2.카피맵 필요 (없었다. 왜냐면 맵을 조작해서 푸는 문제가 아니고 사다리를 기준으로 좌표만 움직이니까)
3.사다리타서 맨아래로 내려오는 시뮬레이션 필요
실수한거
4.마지막줄 계산안했음.
5.사다리가 전부 1이라 왼쪽오른쪽 어디로 갈지를 못정했다.
중복순열로 되서 시간 초과가 났던거 같은데..
*/
 
int N, M, H;
int map[31][11]; //H , N
bool END = false; //재귀함수를 멈추는 조건문
int ans = -1;
 
void dfs(int c,int len,int m) {
    if (len == m) {
        
        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            //사다리 타기 시뮬레이션    
            int r = 1, c = i; //시작점세팅(가로번호 세로번호)
            while (r != H + 1) { //마지막행까지 사다리타기가능
                if (map[r][c] != 0) {
                    int check = map[r][c];
                    if (map[r][c - 1] == check) c--;
                    else if (map[r][c + 1] == check) c++; //if와 else if의 차이...캬(둘다실행하느냐,하나만실행하느냐)
                    r++;
                }
                else r++;
            }
            if (i == c) cnt++;
        }
 
        if (cnt == N) { END = true; ans = len; } //모두 도착한것이 맞을때    
        return; 
    }
 
    for (int i = 1; i <= H; i++) {
        for (int j = c; j < N; j++) { //c부터 쭈루룩 앞으로 가면서 조합구현
            if (map[i][j] == 0 && map[i][j + 1] == 0 && END == false) { //아직 성공하지 못한경우만 진행
                map[i][j] = j; map[i][j + 1] = j; //세로번호로 등록
                dfs(j, len + 1, m);
                map[i][j] = 0; map[i][j + 1] = 0;
            }
        }
    }
}
 
 
int main()
{    
    cin >> N >> M >> H;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;//b번세로선과 a번 점선 위치
        map[a][b] = b; //세로번호로 등록
        map[a][b + 1] = b;
    }
    
    //통과를 못한경우에만 계속 진행
    for (int i = 0; i <= 3; i++) { if (END == false)dfs( 1, 0, i); }
    printf("%d\n", ans);
 
    return 0;
}