[BOJ] 15684 사다리조작 - Java

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

15684번: 사다리 조작

[풀이]

문제를 보고 키보드를 잡기까지 상당한 시간이 걸렸다. 어떻게 풀이 방법을 생각해야할지를 모르겠었기 때문이다

처음에는 다음과 같이 생각했다. 홀수개의 사다리 선이 있으면 i -> i 제자리로 돌아올 수 없으므로 홀수인 애들한테 가서 dfs를 돌리면 되지 않을까? 

그래서 짝수인 경우는 사다리를 놓지 않고, 홀수인 경우에만 하나씩 놓아서 문제를 해결하려 해보았다. 그런데 테케는 다 맞았지만 내자마자 틀렸습니다 가 떴다. 그도 그럴 것이 무조건 홀수에다가만 놓는 것이 능사가 아니다. 짝수에 놔야 할 수도 있고, 홀수에 1개가 아닌 그 이상을 놓아야 할 수도 있다. 그렇기 때문에 완전탐색을 해야한다는 결론을 내었다.

 

이후에는 아래 그림과 같이 좌표로 보고 풀기 시작했다. 세로 1~2 사이에 있는 애들은 col 1로 보고 완전탐색 dfs를 시작해보자!

1. 놓을 수 있는 사다리 개수의 최소 값을 찾는 것이므로 맨처음에 완성되어 있는지를 확인한다. -> 0출력 후 종료

2. 완성이 아니면 1개부터 3개까지(num) 놓기 시작한다. -> newDfs 고고

3. 완전탐색을 하며 놓은 사다리 개수(count)가 num 이상이 되면 완성되어 있는지를 확인한다. (isRight) -> count 출력 후 종료 (최소 갯수를 구하는 것이므로 이상은 볼 필요 없음)

4. 아니면 계속 진행

[코드]

import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Boj15684_사다리조작 {
    static StringTokenizer st;
    static int N,M,H;
    static ArrayList<Integer>[] Arr;
    static int answer = Integer.MAX_VALUE;
    static boolean[][] visit;

    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("src/main/java/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); //세로
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken()); //가로
        visit = new boolean[H+1][N]; //방문 배열

        Arr = new ArrayList[N+1];
        for(int i=0;i<N+1;i++){
            Arr[i] = new ArrayList<>();
        }

        for(int i=1;i<M+1;i++){
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            Arr[col].add(row); //col~col+1에 row번째 사다리가 존재한다.
            visit[row][col] = true; //방문처리
        }

        if(isRight()){ //맨처음 상태 체크
            System.out.println(0);
            return;
        }

        for(int i=1;i<=3;i++){ //사다리 i개 설치하는 경우
            newDfs(1,1,0,i);
        }

        if(answer==Integer.MAX_VALUE){ //갱신이 이루어지지 않은 경우는 불가능한 경우
            System.out.println(-1);
        }
    }

    static void newDfs(int C,int R, int count,int num){
        if(count >= num){
            if(isRight()){ //i번째가 i번째에 도달하는지 확인
                answer = Math.min(answer,count);
                System.out.println(answer);
                System.exit(0);
            }
            return;
        }
        if(count>3){
            return;
        }

        for(int col=C;col<N;col++){ //세로
            for(int row=R;row<H+1;row++){ //가로
                if(!visit[row][col]){ //방문체크
                    if(isOk(col,row)){ //놓을 수 있는지 체크(양옆에 사다리 있니?)
                        visit[row][col] = true;
                        Arr[col].add(row);
                        newDfs(col,row,count+1,num);
                        Arr[col].remove(Arr[col].size()-1); //백트래킹
                        visit[row][col] = false;
                    }
                }
            }
            R = 1; //다음은 row가 다시 1부터 시작해야 하므로
        }
    }

    static boolean isRight(){ //i가 i로 도착하는지 확인
        for(int i=1;i<=N;i++){
            int now = i;

            for(int row = 1;row <= H;row++){ //가로 한 칸씩 내려가면서 i가 어디로 가있는지 확인하자
                int front = now-1; //왼쪽 사다리 볼거임
                int back = now; //오른쪽 사다리 볼거임
                if(0<front && front<=N-1){ //범위 체크
                    for(int item:Arr[front]){ //front~front+1사이에 사다리가 있을 때 row번째 애인지 체크
                        if(item==row){
                            now = front; //있으면 거기로 이동
                            break;
                        }
                    }
                }
                if(0<back && back<=N-1){
                    for(int item:Arr[back]){
                        if(item==row){
                            now = back+1; //있으면 거기로 이동
                            break;
                        }
                    }
                }
            }
            if(now!=i){ //i가 i로 오지 않았으면 false 리턴
                return false;
            }
        }
        return true; //다 i로 무사히 온 것이므로 true 리턴
    }

    static boolean isOk(int col, int row){ //col~col+1의 i번째 가로에 사다리를 놓을 수 있을까?
        //col 앞,뒤를 봐서 i가 존재하는지 확인 -> 존재하면 false 존재하지않으면 true
        int front = col-1; //col의 앞 사다리
        int back = col+1; //col의 뒷 사다리
        if(0<front && front<=N-1){ //범위체크
            for(int item:Arr[front]){
                if(item==row){
                    return false;
                }
            }
        }
        if(0<back && back<=N-1){
            for(int item:Arr[back]){
                if(item==row){
                    return false;
                }
            }
        }
        return true;
    }
}