[백준] 15684_사다리 조작(DFS) java

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

15684번: 사다리 조작

문제

• N x M 사다리가 주어진다. N은 세로선, M은 가로점선이다. 위는 N=5, M=6이다.
• H는 6이다. (가로실선을 놓아 연결할 수 있는 최대 갯수)

• 초록선은 세로선이며, 점선은 가로선이다. 가로선은 인접한 두 세로선사이를 연결해야한다. 단, 두 가로선이 연속하거나 서로 접하면 안된다.

• 1번말은 3번으로 갔고, 2번말은 2번으로 갔다.
• 사다리를 가로선에 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때 i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해 추가해야하는 가로선 갯수의 최소값을 구하는 프로그램을 작성하시오.

입력 예시	설명
	가로선의 정보는 a, b로 주어진다. b번 세로선과 b+1 세로선을 a번 점선 위치에서 연결했는의미이다. ex) 5 1 : 1번과 2번 세로선을 5번 가로선에서 연결한다. 2 3 : 3번과 4번 세로선을 3번 가로선에서 연결한다.

출력

• i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최소값을 출력한다. 만약 정답이 3보다 크면 -1을 출력한다. 또 불가능한 경우에도 -1을 출력한다.

 풀이방법

• 당연히 최소라는 말이 많이 나와 bfs로 접근했지만 시간초과 뜸.
• dfs로 접근
• check 함수 생성 (가로선을 그을 때 마다 가능한지 여부 체크)
• 모든 경우에 가로선을 하나 씩 늘려감

Check 함수

• 세로줄을 검사하면서 1을 만나면 우측으로(y++), 2를만나면 좌측으로(y--) 해준다.
• 해당 말의 결과와 숫자가 같으면 true 해주고 계속 다른 말 검사, 해당 말의 결과와 숫자가 다르면 바로 false return

public static boolean check(){
        for(int i =0  ; i < n ; i++){ 
            int x = 1, y = i;  // 가로줄1번부터 시작, y는 말
            for(int j = 0 ; j < h ; j++){
                if(map[x][y] == 1) {  //만약 해당 칸이 1이면 우측으로 이동 = y++
                    y++;
                }
                else if(map[x][y] ==2){
                    y--;   //만약 해당 칸이 2면 왼쪽으로 이동 y--;
                }
                x++; //만약 해당 칸에 가로선이 없으면 아래로 이동
            }
            if(y != i) return false; // 결국 해당 말이 결과가 다르다면 바로 false
        }
        return true;
    }​

 

dfs 부분

• 가로선을 그을 수 있는 곳 (=map[i][j] = 0 && map[i][j+1] ==0 인곳)에 모두 가로선을 그어준다.
• 가로선을 긋고 바로 check해준다. 되면 해당 count값을 반환 안되면, 가로선을 그을 수 있을 만큼 계속 그어준다.

 public static void dfs(int x, int count){
        if(answer < count) return ;  
        else{
            if(check()){
                answer = count;
                return;
            }
        }
        for(int i = x ; i < h + 1 ; 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,count+1);
                    map[i][j] = map[i][j+1] = 0 ;
                }
            }
        }

    }