백준 15684번 사다리 조작

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Ladder_Operation {
    static int N;
    static int M;
    static int H;
    static int[][] map;
    static boolean finish = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new int[H+1][N+1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            map[row][col] = 1;
            map[row][col+1] = 2;
        }
        for (int i = 0; i < 4; i++) {
            dfs(0,0,0,i);
        }
        System.out.println(-1);
    }
    public static void dfs(int row, int col, int count, int size){
        if(count == size){
            if(check()){
                System.out.println(count);

                System.exit(0);
            }
            return;
        }
        for (int i = row; i <= H; i++) {
            for (int j = 1; j < N; j++) {
                if(map[i][j]==0&&map[i][j+1]==0){
                    map[i][j] = 1;
                    map[i][j+1] = 2;
                    dfs(i,j,count+1,size);
                    map[i][j] = 0;
                    map[i][j+1] = 0;
                }
            }
        }
    }
    public static boolean check(){

        for (int i = 1; i <= N; i++) {
            int row = 1;
            int col = i;
            while(true){
                if(row==H+1){
                    if(col == i){
                        break;
                    }
                    else {
                        return false;
                    }
                }
                if(map[row][col]==1){
                    col++;
                }
                else if(map[row][col]==2){
                    col--;
                }
                row++;
            }
        }
        return true;
    }
}

풀이 방법

📢 이 풀이의 핵심은 사다리하나를 왼쪽에서 지날때, 오른쪽에서 지날때 나누어서 체크하는 것이다.
1. 처음 주어지는 사다리의 위치를 좌표에 1로 표현한뒤 바로 한칸 오른쪽에는 2로 표현한다.(사다리가 1을 만나면 오른쪽으로 가고, 2를 만나면 왼쪽으로 구현하게 하기 위함)
2. 놓아야하는 사다리가 3개가 넘어가면 전부 -1로 체크해야 하므로 탐색은 0~3까지만 탐색한다.
3. 크게 보면

• i번이 i번으로 가는지 확인한다.
• 첫번째 추가 사다리를 놓는다.
• 다시 i번이 i번으로 가는지 확인한다.
• 3번까지 반복해보고 안되면 -1, 그전에 i번이 i번으로 간다면 탐색을 중지한다.

4. dfs탐색은 현재 위치와 오른쪽 위치가 둘 다 0이라면 사다리를 놓는다.
5. count를 1증가시키고 사다리를 다시 놓는다. 이때 백트래킹시 사다리를 다시 원상 복구시켜 놓는다.(👆사다리는 위에서부터 내려오면서 놓으므로 내위치 보다 위쪽은 더이상 탐색할 필요가 없다. for( i= row; ; ;))
6. 사다리 갯수가 처음 조건에 맞는다면 check함수를 통해 i번이 i번으로 가는지 확인한다.
7. check 함수는 마지막 행까지 탐색하고 그때의 col값이 i가 아니라면 false를 리턴한다.
8. 탐색시에는 1이면 오른쪽으로 2이면 왼쪽으로 이동하고 아래로 한칸 이동하도록 탐색한다.

후기

내 위치 보다 위쪽을 다시 탐색할 필요가 없다는 점이 중복을 줄이는 방법이었고 실제로 시간복잡도 차이가 많이 난다.
저번에 비슷한 문제를 경험했었는데 이번에 찾아내지 못한점이 아쉬웠다.