[백준 15684 : JAVA] 사다리 조작 / 백트래킹

문제

---

 

 

 

풀이

---

개인적으로 되게 어려웠던 문제였다. 풀이를 보면서도 많은 시간 고민했다.

 

첫 번째로 고민했던건 주어지는 가로선의 정보를 어떤 식으로 저장할까였다. 

그동안 풀었던 문제는 대게 칸으로 주어졌기 때문에 별 생각없이 map[y][x] 에 저장하면 됬지만, y축과 x축이 칸이 아닌 선으로 주어져서 고민했는데, 그냥 아래처럼 칸이라 생각하고 똑같이 저장하면 되겠다라고 생각이 들었다.

 

[그림 1] map 구조

 

위의 그림에서 최상단 좌측을 (1, 1)이라 두고, 값이 저장되는 세 가지 경우를 나눴다.

0 : 해당 칸에는 가로선이 없다.

1 : 해당 칸을 기준으로 우측으로 연결되는 가로선이 있다.

2 : 해당 칸을 기준으로 좌측으로 연결되는 가로선이 있다.

 

1번 높이의 1번과 2번 세로선을 연결하는 가로선이 있다면, map[1][1] = 1; map[1][2] = 2; 이런 식으로 저장했다.

 

그런 다음 i번에서 출발해 i번에 도착하는지 확인하는 체크 용도의 함수가 필요한데, 아래와 같은 코드로 체크했다.

private static boolean check() {
    for (int i = 1; i <= width; i++) {
        int nx = i;
        int ny = 1;

        while (ny <= height) {
            if (map[ny][nx] == 1) nx++; // 우측으로 이동
            else if (map[ny][nx] == 2) nx--; // 좌측으로 이동
            ny++; // y축+1칸 이동한다. (아래로 이동)
        }

        if (nx != i) return false; // i번으로 출발해서 i번으로 도착하지 않는게 하나라도 있다면 리턴.
    }

    return true;
}

 

마지막으로 DFS 탐색의 파라미터로 추가할 가로선의 수를 지정해줘야한다. 이게 DFS 탐색의 종료 조건이 되기 때문이다.

최대 3개의 가로선을 추가할 수 있으므로, 이를 반복문으로 놔두고 각 내부에서 DFS를 호출하는 방법을 이용했다.

 

 

 

코드

---

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

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int width, height, M, ans;
    private static int[][] map;
    private static boolean isFinish = false;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        width = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken()); // 연결된 가로선의 갯수
        height = Integer.parseInt(st.nextToken());

        map = new int[height + 1][width + 1];
        for (int y = 0; y < M; y++) {
            st = new StringTokenizer(br.readLine());

            // a 높이에서 b번과 b+1번 세로선을 연결한다.
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b] = 1;     // 1 : 우측으로 이동.
            map[a][b + 1] = 2; // 2 : 좌측으로 이동.
        }

        // 추가할 가로선의 갯수를 미리 정해놔야 탐색 종료 조건으로 걸 수 있다.
        // 아래 반복문에서 i는 추가할 가로선의 수.
        for (int i = 0; i <= 3; i++) {
            ans = i;
            dfs(1, 1, 0);
            if (isFinish) break;
        }

        System.out.println((isFinish ? ans : -1));
        br.close();
    }

    // addHorizontalLineNumber : 추가한 가로선의 갯수 (3개가 넘어가면 더이상의 탐색이 무의미.)
    private static void dfs(int x, int y, int addHorizontalLineNumber) {
        if (isFinish) return;
        if (ans == addHorizontalLineNumber) {
            if (check()) isFinish = true;
            return;
        }

        for (int i = y; i <= height; i++) {
            for (int j = x; j < width; j++) {
                // 가로선 두 개가 연속으로 놓여질 수 없기 때문에 가로선을 추가하기 전에 연결된 가로선이 있는지 확인한다.
                if (map[i][j] == 0 && map[i][j + 1] == 0) {
                    // 가로선을 추가한다.
                    map[i][j] = 1;
                    map[i][j + 1] = 2;

                    dfs(1, 1, addHorizontalLineNumber + 1);

                    // 추가했던 가로선을 다시 제거한다. (백트래킹)
                    map[i][j] = 0;
                    map[i][j + 1] = 0;
                }
            }
        }
    }

    // i번으로 출발해서 i번으로 도착하는지 확인한다.
    private static boolean check() {
        for (int i = 1; i <= width; i++) {
            int nx = i;
            int ny = 1;

            while (ny <= height) {
                if (map[ny][nx] == 1) nx++; // 우측으로 이동
                else if (map[ny][nx] == 2) nx--; // 좌측으로 이동
                ny++; // y축+1칸 이동한다. (아래로 이동)
            }

            if (nx != i) return false; // i번으로 출발해서 i번으로 도착하지 않는게 하나라도 있다면 리턴.
        }

        return true;
    }
}