[JAVA] 15684 - 사다리 타기 💛3 : 백트래킹을 하지 않으면 풀리지 않는 완전탐색 문제

들어가며

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

문제가 좀 길어서 입력값을 이해하는데 꽤 시간이 걸렸다. 간단하게 요약하자면 사다리를 원하는 개수만큼 놓고나서 우리가 흔히 뽑기 할때 하는 게임인 사다라타기를 진행해서(따라다다다단 따라다다다단) 모든 번호가 각자 번호에서 시작하면 자기 번호로 도착해야 하는 사다리게임을 만들어야 한다. 그때 추가해야 하는 가로선 개수의 최솟값을 출력하면 된다(M <= 3).

본문으로

솔직히 처음 읽었을떄 문제 자체가 이해가 안되서 아래처럼 생각나는데로 그리면서 이해하려고 노력했다.(문제를 보면서 필기한거라 글씨체는..ㅎㅎ)

내린 결론은 그냥 완전탐색 문제인데? 하고 재귀함수의 수도코드만 간단하게 작성한다음 아래와 같이 코드를 작성했다.

public class Main {

    static int N, M, H, ret;
    static int[][] maps;
    static int[][] ladder;

    static void go(int idx) {
        if (idx > 3) {
            return;
        }

        if (isOkay()) {
            ret = Math.min(idx, ret);
        }

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N - 1; j++) {
                if (ladder[i][j] == -1 && ladder[i][j + 1] == -1) {
                    ladder[i][j] = j + 1;
                    ladder[i][j + 1] = j;
                    go(idx + 1);
                    ladder[i][j] = -1;
                    ladder[i][j + 1] = -1;
                }
            }
        }

    }

    static boolean isOkay() {
        boolean isHere = true;
        for (int i = 0; i < N; i++) {
            int here = i;
            for (int j = 0; j < H; j++) {
                if (ladder[j][here] != -1) {
                    here = ladder[j][here];
                }
            }
            if (here != i) {
                isHere = false;
            }
        }
        return isHere;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        ret = Integer.MAX_VALUE;

        maps = new int[H][N];
        ladder = new int[H][N];
        for (int i = 0; i < H; i++) {
            Arrays.fill(ladder[i], -1);
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer line = new StringTokenizer(bf.readLine());
            int r = Integer.parseInt(line.nextToken()) - 1;
            int c = Integer.parseInt(line.nextToken()) - 1;
            ladder[r][c] = c + 1;
            ladder[r][c + 1] = c;
        }

        go(0);

        if (ret > 3) {
            System.out.println(-1);
        } else {
            System.out.println(ret);
        }

    }
}

문제에서 제공중인 테스트케이스들은 문제없이 통과하길래 자신있게 제출했다!!!

결과는 시간초과 ㅎㅎ. 이게 바로 시간복잡도 계산도 안해보고 완탐 로직 구현에 들어간 자의 최후이다.

---

잠시 시간복잡도를 계산해보자.

사다리 행렬 N * M의 최대는 300이다. 따라서 전체적인 시간 복잡도는

300(사다리 확인) * 300C3(사다리 뽑기 : 450만정도) =: 10억  정도가 된다.  이걸 미리 계산하고 완탐으로 풀었을 때 안되겠거니.. 하고 꺼림찍한 느낌을 느꼈여야 한다!! 결론은 어떤 알고리즘을 써서라도 시간복잡도를 무조건 줄여야하는 문제였다.

문제에서 다행이게도, 사다리를 놓아야하는 갯수가 3 이상이면 -1을 출력하면 되었다. -> depth가 3이상이면 굳이 더 탐색할 필요 없다 -> 백트래킹

 

그리고 지금 나의 로직은 사다리를 i번째 깊이까지 내려왔으면 i번째 이후만 체크하면 되는 거였는데, 굳이 0부터 체크를 계속 반복하고 있어서 완전 무식한 로직이었다. 그래서 결국 재귀함수 인자에 시작지점을 추가해주어서 시작지점부터 탐색을 진행하게끔 바꾸었다. 

아래는 최종 정답 로직이다.

public class Main {

    static int N, M, H, ret;
    static int[][] maps;
    static int[][] ladder;

    static void go(int here, int idx) {
        if (idx > 3) { 3개이상 놓을 필요없음 (백트래킹)
            return;
        }
        if (idx >= ret) { // 지금 최소보다 사다리를 더 많이 놓을 필요없음(백트래킹)
            return;
        }

        if (isOkay()) {
            ret = Math.min(idx, ret);
            return;
        }

        for (int i = here; i < H; i++) { // here부터 시작(탐색이 필요한 부분만 탐색)
            for (int j = 0; j < N - 1; j++) {
                if (ladder[i][j] == -1 && ladder[i][j + 1] == -1) {
                    ladder[i][j] = j + 1;
                    ladder[i][j + 1] = j;
                    go(i, idx + 1);
                    ladder[i][j] = -1;
                    ladder[i][j + 1] = -1;
                }
            }
        }

    }

    static boolean isOkay() {
        boolean isHere = true;
        for (int i = 0; i < N; i++) {
            int here = i;
            for (int j = 0; j < H; j++) {
                if (ladder[j][here] != -1) {
                    here = ladder[j][here];
                }
            }
            if (here != i) {
                isHere = false;
            }
        }
        return isHere;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        ret = Integer.MAX_VALUE;

        maps = new int[H][N];
        ladder = new int[H][N];
        for (int i = 0; i < H; i++) {
            Arrays.fill(ladder[i], -1);
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer line = new StringTokenizer(bf.readLine());
            int r = Integer.parseInt(line.nextToken()) - 1;
            int c = Integer.parseInt(line.nextToken()) - 1;
            ladder[r][c] = c + 1;
            ladder[r][c + 1] = c;
        }

        go(0, 0);

        if (ret > 3) {
            System.out.println(-1);
        } else {
            System.out.println(ret);
        }

    }
}

마무리하며

백트래킹을 위한 로직들을 재귀함수 곳곳에 넣어줬는데, 머릿속으로 가지를 치는 느낌이 그려져서 매우 좋다..! 앞으로도 결국 다 탐색을 해봐야한다면 시간복잡도를 먼저 계산하고, 혹시 애매하다면 시간복잡도를 줄일 방법을 고민하는 식으로 생각의 흐름을 잡아야겠다.