[백준] 15684번 / Java / 사다리 조작 - DFS, 시뮬레이션, 완전탐색 풀이

문제 - (https://www.acmicpc.net/problem/15684)

문제를 딱 보자마자 "와 이거 어렵겠는데?"라는 생각이 들었다.

왜냐하면 사다리를 타서 i에서 i로 가는 걸 어떻게 확인해야 할지가 막막했기 때문이다.

그런데 이 부분은 막상 구현해보니 어렵지 않았다. 내 코드에서 checkLadder() 함수를 보면 된다.

다른 사람 코드를 보니 나보다 더 간단하게 구현했지만 내 코드도 조건을 확인하는데 지장 없다.

 

그럼 이제 생각해볼 것이,

선을 몇 개 그어야 i에서 i로 가도록 할 수 있겠는가 이다.

보자마자 완전탐색하면 되겠다는 생각이 들었지만... 경우의 수가 너무 많다는 생각이 들었다.

그래서 잘못생각한 줄 알고 고민에 빠져있었는데, 아니나 다를까 문제에 조건이 있었다.

만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

그렇다!

추가할 선이 3개가 넘어가는 경우는 탐색할 필요가 없다... 조건을 꼭 반드시 무조건 숙지하고 문제를 풀자 ㅠㅠ.

가로선(H)을 조회해가면서 선을 그리고, 조건을 체크하면 끝이다.

 

이렇게 까지만 하면,,, 정답은 맞히지만 시간이 13초 이상이 걸린다.

무언가 개선이 필요하다고 느꼈지만 모르겠어서 다른 사람의 코드를 확인했다. (그분은 88ms 였다. ㄷㄷㄷ)

 

내가 빼먹은 것은 바로!

"추가할 선의 갯수"를 고려하지 않은 것이다.

문제에서는 

추가해야 하는 가로선 개수의 최솟값을 출력한다.

라고 했다. 이 말인 즉, 선을 0개 추가했을 때 조건을 만족하면 답은 0이 되고 더 이상 탐색할 필요가 없다는 뜻이다.

그런데 나는 1개 추가했을 때 조건 만족하는걸 발견했음에도, 2개, 3개를 추가한 경우도 굳이 확인해서 하지 않아도 될 탐색을 진행해버리니 시간이 오래 걸린 것이다.

따라서 탐색할 때 선의 갯수를 0 1 2 3 개 순서로 추가할 수 있게 해서 중간에 한 번이라도 조건을 만족해서 true가 리턴되면 탐색을 종료하고 그 수를 반환하면 끝이다.

---

📌주의할 점

• 항상 문제의 입력, 출력 조건을 숙지하고 문제를 푼다.
• 너무 어렵게 생각하지 말자... 문제에서 제시한 것을 구현할 때 무식하게 그대로 옮기려고 하지 말고 규칙을 찾아내서 더 쉽게 구현할 수 있는 방법을 생각해보자.

---

😅실수

• 구현 시 반복문이 필요하다면 쉽더라도 반드시 손으로 써보고 코딩하자! 쉽다고 생각해서 바로 코딩을 시작했는데, 막상 코드로 옮기니 헷갈려서 시간을 잡아먹기도 한다.
• 이번에도 설계를 완벽히 하지 않고 어느정도 설계한 다음에 문제를 풀면서 수정해나가는 식으로 진행했다... 문제를 풀다가 수정이 필요하다고 느껴지면 다시 펜을 잡고 손으로 풀어보자!!! 이번에는 운 좋게 머릿속으로 진행한 것이 정답이었지만, 만약 아니었다면 시간 엄청 잡아먹었을 것이다.

 

---

코드

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

/**
 * 1시간 25분
 * 메모리 : 16564kb
 * 시간 : 1348ms
 *
 * -- 개선 --
 * 메모리 : 15884kb
 * 시간 : 340ms
 * 문제에서 "정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다"라는 조건이 있으므로
 * 선을 0~3개 순서로 그리다가 한 번이라도 조건에 만족한다면 더이상 탐색할 필요가 없이 그것이 정답이 된다.
 * 따라서, 더이상의 탐색을 중단함으로써 시간을 개선했다.
 */
public class Ladder {
    static int N;
    static int M;
    static int H;
    static int[][] map;
    static int answer = Integer.MAX_VALUE;
    static int drawNumber = 1;

    // 가능한 모든 경우를 구하자
    static boolean dfs(int y, int addLine, int size /* 사다리에 그을 수 있는 선의 수 */) {
        // 기저
        if (addLine == size) {
            if (checkLadder()) {
                answer = Math.min(answer, addLine);
                return true;
            }
            return false;
        }

        // 사다리에 가로선 그리기
        for (int i = y; i <= H; i++) {
            for (int j = 1; j < N; j++) { // 마지막은 선을 그을 수 없으므로 j < N
                int current = map[i][j];
                int next = map[i][j + 1];
                if (current != -1 || next != -1) continue;
                addLine(i, j);
                /* 한 번이라도 조건에 만족해서 true가 리턴된다면 더이상 탐색할 필요 없음 */
                if (dfs(i, addLine + 1, size)) return true;
                removeLine(i, j);
            }
        }
        return false;
    }

    static void addLine(int y, int x) {
        drawNumber++;
        map[y][x] = drawNumber;
        map[y][x + 1] = drawNumber;
    }

    static void removeLine(int y, int x) {
        map[y][x] = -1;
        map[y][x + 1] = -1;
    }

    static boolean checkLadder() {
        // i가 i로 가는지 확인
        for (int x = 1; x <= N; x++) {
            int cursor = x;
            for (int y = 1; y <= H; y++) {
                int current = map[y][cursor];
                if (current != -1) {
                    // 연결된 선 찾으면 연결된 곳으로 이동
                    if (cursor - 1 >= 1 && map[y][cursor - 1] == current) {
                        // 좌로 연결된 경우
                        cursor = cursor - 1;
                    } else if (cursor + 1 <= N && map[y][cursor + 1] == current) {
                        // 우로 연결된 경우
                        cursor = cursor + 1;
                    }
                }
            }
            if (cursor != x) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        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());

        map = new int[H + 1][N + 1];
        // 맵 초기화
        for (int[] m : map) Arrays.fill(m, -1);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x1 = Integer.parseInt(st.nextToken());
            int x2 = x1 + 1;
            map[y][x1] = drawNumber;
            map[y][x2] = drawNumber;
            drawNumber++;
        }

        /* 사다리에 선을 그을 수 있는 갯수를 지정 */
        for (int i = 0; i <= 3; i++)
            if (dfs(1, 0, i)) break;
        System.out.println(answer > 3 ? -1 : answer);
    }
}