[백준] 15684번 사다리 조작

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/swtest/Q15684.java

사다리의 상태가 주어진다. 새로운 가로줄을 최대 3개까지 그을 수 있을 때, i번째 시작이 i번째 도착지에
도착하도록 사다리를 조작하여라 불가능한 경우 -1을 출력한다.

처음 생각

생각보다 정답률이 낮은 문제이므로 최대한 직관적으로 볼 수 있도록 풀어보았다. 우선 처음드는 생각은 이 사다리의 연결 상태를 어떻게 표현해 줄 것이가에 대한 생각이 들었다. 다양한 방법들이 있을 것이다. 2차 배열을 이용해서 1과 2가 연결되어있으면 arr[1][2]=1, arr[2][1]=1로 표현을 해도되고(실제로를 가로줄의 위치가 있으니 3차 배열일 것이다.) 배열을 리스트로 만들어도 될 것이다. 요렇게 저렇게 다양한 방법으로 만들어 볼 수 있지만 결국 사다리이므로 사다리를 만들어 주었다.

▶ 2차 배열에 사다리를 만들어 주었다. 일반적인 사다리 게임을 생각하면서 만들어보자. 3개의 세로줄이 있다고 생각해보면, 아래 그림처럼 그 사이사이에 2개의 통로가 생긴다. 또, H개의 가로줄이 있다고 생각하면 시작 번호가 적힌줄 끝나는 줄을 생각해보면 위 아래로 2개의 칸이 더 있어야 한다. 따라서 다음과 같은 모양으로 만들어 줄 수 있다. 여기서 0은 입력으로 주어지는 이동할 수 있는 통로를 의미한다.

다음 생각

이동 통로는 항상 이동해 다닐 수 있는곳이 아니므로 초기에는 모두 -1로 이동하지 못하도록 아래와 같이 채워넣어 주었다.

다다음 생각

이제 입력에서 주어지는 M개의 미리 이어져 있는 통로를 반영해 주어야한다. 이 때, 조심해야하는 점이 사다리 게임에서 가로로 2개의 줄이 이어져 있는 경우는 없다. (요 조건은 문제에서도 말해주고 있다.) 즉, 주어진 조건의 값이 들어왔다면 그 가로줄의 왼쪽 오른쪽 가로줄은 건드릴 필요가 없다는 것이다. 따라서 이런 경우는 아래와 같이 아예 건들지 말라는 뜻으로 -3으로 변경시켜주었다.

▶ 노란색으로 표시된 곳이 미리 주어지는 공간이라면 주황색으로 표시된 곳은 변경시키면 안되므로 -3으로 지정해 주었다.

다다다음 생각

이제 DFS 탐색을 통해서 조건들을 만들어 주어야 한다. 조금 난해한 점이라면 H*(N-1) 개중 최대 3개를 고르는 것이라 생각한다. 앞서 치킨 배달([백준] 15686번 치킨 배달) 같은 문제를 보면 1차에서 생각하므로 접근하기가 이 경우보다는 쉬웠을 것이다. 하지만 지금은 사다리이므로 가로줄과 함께 세로줄도 포함해서 생각해 주어야한다. 언뜻보면 난해하지만 알고나면 그렇게 난해 하지않다는 것을 알 수 있다. 약간의 코드와 함께 살펴보면 이해가 좀 더 쉽다.

// 해당 열을 넘으면 넘으면 다음 줄로 이동
if(y>n-1) {
    solve(x+1, 1, cnt);
    return;
}

▶ solve 메소드는 다음과 같다. solve(행 번호, 열 번호, 선택 개수) 이 때 세로줄을 우선시 해도 상관없지만 가로줄을 우선시 해서 해당 가로줄이 -1로 되어있어 변경 가능할 경우 0으로 변경 해준 후 solve(행 번호, 열 번호+4, 선택 개수) 로 다음 탐색을 진행해 나아갔다. 열 번호 +4의 이유는 위에서 보았듯 하나가 연결이 되면 그 양옆 가로줄은 변경할 필요가 없기 때문이다. 마찬가지로 변경을 안하고 넘어간다면 다음껄 변경시켜도 되므로 열 번호 +2로 진행하였다.

▶ 열 번호가 더해지면 나아가다 위의 코드와 같이 해당 열을 넘으면 solve(행 번호 +1, 열의 처음시작 1, 선택 개수)를 넘겨 주어 자연스럽게 다음 줄을 탐색 하도록 하면된다.

▶ 마찬가지로 행도 범위를 초과하지 않도록 아래와 같이 처리를 해주었다.

// 마지막 줄 아래로 이동 방지
if(x>=h-1) return;

다다다다음 생각

이제 모든 경우마다 i번째 줄에서 시작해서 i번째 줄로 갈 수 있나 판단을 해주어야한다. 길이 무조건 한 가지이므로 DFS 탐색을 하였다. 방문 체크를 해나가면서 탐방을 해야하고, 여러 방향을 봐야하는 경우가 없기 때문에 BFS 탐색을 이용하지 않았다.

▶ 위의 완전 탐색의 조건을 만들어주면 1번쪽 즉, 왼쪽꺼부터 다리를 놓는다. 따라서 예제에 따라 다르긴 하겠지만 i번째 줄로 갈 수 있나의 판단을 1번부터가 아닌, 뒤에서 부터 진행을 해주면 불가능한 경우를 좀 더 빨리 return 시킬 수 있다. 실제로 백준 케이스에서 이 둘의 차이는 1초나 났다.

다다다다다음 생각

모든 케이스를 돌았은데 result의 값이 초기값에서 변경되지 않았다면 -1을 출력하였다.

▶ 초기값은 가장 최소값을 찾아주는 것이기 때문에 최대 놓을 수 있는 개수가 3개까지이므로 4로 정해놓았다.

방안

1) 문제가 난해하다 생각이 들면 케이스를 키워서 직관적으로 볼 수 있게 만들어주는 것도 방법이다. 단, 시간에 있어서는 조금 느릴 수 밖에 없다.

▶ 완전 탐색으로 나온 문제인 만큼 시간은 넉넉히 주니 걱정할 필요는 없을 것 같다.

2) DFS 탐색의 경우 가지 치기가 매우 중요하다. 따라서 return 시켜줄 수 있는 조건이 생각 날때마다 하나씩 바로바로 추가해 주는것이 좋다.

▶ 이 문제의 경우 개수의 최소값을 찾는 것이므로 한 번 개수가 정해지면 그 개수보다 같거나 큰 개수들은 살펴볼 필요가 없다.

package baekjoon.swtest;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q15684 {
    static int n,m,h;
    static int[][] arr;
    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()); // 세로선 마다 가로선을 놓을 수 있는 위치 개수
        // n과 h값 바꾸기
        n = 2*n-1;
        h = h+2;
        // 사다리를 표로 만들자
        // 세로 h+2(숫자표시) & 가로 n개+n-1칸들
        visited = new boolean[h][n];
        arr = new int[h][n];
        
        // 숫자 표시(출발 &도착) 첫 줄과 끝 줄 숫자 넣어주기
        for(int i=0,j=1;i<n;i+=2) {
            arr[0][i]=j;
            arr[h-1][i]=j++;
        }
        
        // 라인이 그려져야하는곳 -1로 채우기
        for(int i=0;i<h;i++) {
            for(int j=1;j<n;j+=2)
                arr[i][j] = -1;
        }
        
        // 주어지는 가로선 채우기 숫자 중간 중간이므로 홀수 배열로 찾아가도록
        // 1 3 5 7 9 11 ...
        int[] holsu = new int[31];
        for(int i=1,j=1;i<=30;i++,j+=2)
            holsu[i] = j;
        
        for(int i=0;i<m;i++) {
            st = new StringTokenizer(br.readLine());
            int pick = Integer.parseInt(st.nextToken());// 가로줄 번호
            int num = Integer.parseInt(st.nextToken()); // 세로줄 번호
            num = holsu[num];
            arr[pick][num] = 0;
            // 미리 그어저 있는 선의 양 옆은 건들지 못한다.
            // 범위를 벗어날 수도 있으니 try catch로 처리
            try {arr[pick][num+2] = -3;}catch (Exception e) {}
            try {arr[pick][num-2] = -3;}catch (Exception e) {}
        }
        // 답 최대 3개이므로 4로 설정
        result = 4;
        solve(1, 1, 0);
        // 그대로 4라면 불가능 한 것 
        if(result==4) result = -1;
        System.out.println(result);
    }
    
    static boolean flag;
    private static boolean check() {
        // i=0부터 시작 안하고 뒤에서 부터 시작 시키자
        // DFS를 통해 만들어지는 경우의 수가 앞에서부터 생성이 되므로, 뒤에서 부터 보면 안되는 경우를 빨리 쳐낼 수 있다.
        for(int i=n-1;i>=0;i-=2) {
            flag = false;
            visited[1][i] = true;
            dfs(1,i,i);
            visited[1][i] = false;
            if(!flag) return false;
        }
        return true;
    }
 
    // 사다리이므로 왼쪽 오른쪽 아래만 보면된다.(우 좌 하)
    static int[][] dir = {{0,1},{0,-1},{1,0}};
    static boolean[][] visited;
    private static void dfs(int x,int y,int num) {
        for(int i=0;i<3;i++) {
            int tx = x+dir[i][0];
            int ty = y+dir[i][1];
            if(ty<0 || ty>=n) continue;
            if(arr[tx][ty]<0) continue;
            if(visited[tx][ty]) continue;
            if(arr[tx][ty]>0) {
                if(ty==num) flag = true;
                return;
            }
            visited[tx][ty] = true;
            dfs(tx, ty,num);
            visited[tx][ty] = false;
            return;
        }
    }
    
    
    static int result;
    private static void solve(int x,int y,int cnt) {
        // 기존 값과 cnt를 비교해서 cnt가 작은 경우만 찾으면 되므로 다른 조건들은 return 시킨다.
        if(result<=cnt) return;
        
        // 3개 이하로 들어오면 계산
        if(cnt<=3) {
            if(check()) {
                result = Math.min(result, cnt);
                return;
            }
        }
        // 3개 이상이면 return
        if(cnt>=3) return;
 
        // 마지막 줄 아래로 이동 방지
        if(x>=h-1) return;
        
        // 해당 열을 넘으면 넘으면 다음 줄로 이동
        if(y>n-1) {
            solve(x+1, 1, cnt);
            return;
        }
 
        if(arr[x][y]==0) {
            // 이미 이어진 경우 패스하도록 +4.
            solve(x, y+4, cnt);
        }else if(arr[x][y]==-1) {
            // 바꿔도 되는 칸의 경우
            arr[x][y] = 0;
            solve(x,y+4,cnt+1);
            arr[x][y] = -1;
            // 연속된 가로선이 안되도록 2칸이동
            solve(x,y+2,cnt);
        }else if(arr[x][y]==-3) {
            // 건들면 안되는 칸의 경우
            solve(x,y+2,cnt);
        }
    }
    
    static class Pair{
        private int x,y;
        Pair(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}