[백준 Baekjoon] 15684번 사다리 조작 - JAVA

백준 Baekjoon 15684번 사다리 조작 - JAVA

---

문제 풀이

구현 + dfs + 완전탐색 문제이다. 문제가 길고 복작해서 정말 읽기 싫은 문제였다.
최대 사다리를 3개까지 놓아 i번째 사다리가 i번으로 가게 만드는 문제이다.


사다리를 입력 받을 때 양측 통행{(x,y), (x,y+1)}이 가능하도록 놓는 것이 편하다.
i번에서 i번 탐색 시 좌 우 어느 방향으로 이동해야 하는지 알 수 있으며, 이렇게 하면 검사시 두 점을 검사하는 것으로 두 가로선이 연속하거나 접하지 않게 놓을 수 있다.


사다리를 최대 3개까지 놓을 수 있어 0 ~ 3개를 놓는 경우를 dfs로 검사한다.
dfs 탐색 시 이미 검사한 가로선 위치(i)를 매번 검사하지 않도록 i = h에서 검사하게 한다.


x는 세로 높이가 되고 y는 가로 위치이다. 사다리가 놓아져 있는 방향을 보고 좌 우 이동후 마지막에 제자리로 돌아왔는지 비교한다.

소스 코드

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

public class Main {
    public static int N, M, H;
    public static int[][] map;

    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());

        map = new int[H + 1][N + 1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            map[x][y] = 1;
            map[x][y + 1] = -1;
        }

        for (int i = 0; i <= 3; i++) {
            if (dfs(1, 0, i)) {
                return;
            }
        }

        System.out.println(-1);
    }

    public static boolean dfs(int h, int depth, int level) {
        if (depth == level) {
            if (check()) {
                System.out.println(level);
                return true;
            }

            return false;
        }

        for (int i = h; i <= H; i++) {
            for (int j = 1; j < N; j++) {
                if (map[i][j] == 0 && map[i][j + 1] == 0) {
                    map[i][j] = 1;
                    map[i][j + 1] = -1;

                    if (dfs(i, depth + 1, level)) {
                        return true;
                    }

                    map[i][j] = map[i][j + 1] = 0;
                }
            }
        }

        return false;
    }

    public static boolean check() {
        for (int i = 1; i <= N; i++) {
            int y = i;

            for (int x = 1; x <= H; x++) {
                if (map[x][y] == 1) {
                    y++;
                } else if (map[x][y] == -1) {
                    y--;
                }
            }

            if (y != i) {
                return false;
            }
        }

        return true;
    }
}