[JAVA] 백준 사다리 조작

DFS를 이용한 문제이다.

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

처음에는 사다리타기의 경우의 수를 구하는것이 너무 많다고 생각했는데, 문제에서 다리를 3개보다 많이 추가해야되는 경우는 -1로 출력하라는 조건이 더해져서 효율성에 대한 부담을 덜었다.

 

<실행순서>

1. main문에서 추가하는 다리의 개수를 0,1,2,3개에 대하여 dfs를 각각 시도한다.

그 이상의 경우는 출력을 -1로 통일한다.

 

2. 사다리를 추가하는것은 dfs메소드로 추가한 다음, 해당 경우가 i번째 는 i번째에 도착하는지 check메소드로 확인한다.

 

3. 만약 check 메소드로 위 조건이 일치한다면 true를 반환하여 종료시킨다.

 

 

 

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

public class Main {
    static int N, M, H, answer;
    static int[][] info;
    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());
        info = new int[H+1][N+1];
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            info[x][y] = 1;
            info[x][y+1] = 2;
        }

        for(int i=0; i<=3; i++){//depth=3까지만 탐색 그이후로 -1출력
            answer = i;
            dfs(1,0);
            if(finish) break;
        }

        System.out.println((finish) ? answer  : -1);
    }

    static void dfs(int x, int count){
        if (finish) return;
        if(answer==count){
            if(check()) finish=true;
            return;
        }

        for(int i =x; i<H+1; i++){
            for(int j= 1; j<N; j++){
                if(info[i][j]==0 && info[i][j+1] ==0){
                    info[i][j]=1;
                    info[i][j+1]=2;
                    dfs(i, count+1);
                    info[i][j] = info[i][j+1] =0;
                }
            }
        }
    }

    static boolean check(){
        for(int i=1; i<=N; i++){
            int x=1, y=i;
            for(int j=0; j<H; j++){
                if(info[x][y]==1) y++;
                else if(info[x][y]==2) y--;
                x++;
            }
            if(y!=i) return false;
        }
        return true;
    }
}