[백준] 15684번: 사다리 조작 - java

문제

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

15684번: 사다리 조작

 

접근법

N이 10이하, H가 30이하이기 때문에 완전 탐색으로 풀어도 되겠다고 생각했다. 그리고 놓여진 가로선의 개수가 최솟값보다 큰 경우와 3보다 큰 경우를 가지치기 할 수 있기 때문에 백트래킹을 사용했다.

 

문제에서 보여주고 있는 사다리를 2차원 배열로 표현하였고, 아래와 같이 배열의 값을 통해 사다리 존재 여부를 판단했다. 

• 0: 빈칸
• 1: 왼쪽으로 이동할 수 있는 사다리 존재
• 2: 오른쪽으로 이동할 수 있는 사다리 존재

 

이렇게 표현할 경우, 배열의 값이 0이 아닌 구역에 사다리를 놓게 되면 사다리가 겹치게 된다. 따라서 배열의 값이 0인 구간에만 사다리를 놓도록 코드를 작성하였다.

 

코드

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

public class Main {

    static int N, M, H;
    static int[][] ladder; // 0: 빈 칸 / 1: 왼쪽으로 / 2: 오른쪽으로
    static int answer = 4;

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

        ladder = new int[H + 1][N + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            ladder[a][b] = 2;
            ladder[a][b + 1] = 1;
        }

        dfs(1, 1, 0);

        if (answer == 4) {
            System.out.println(-1);
        } else {
            System.out.println(answer);
        }
    }

    private static void dfs(int r, int c, int cnt) {
        if (pass()) {
            answer = Math.min(answer, cnt);
            return;
        }

        // 정답이 3보다 크거나, 최솟값보다 큰 경우
        if (cnt >= 3 || cnt >= answer) {
            return;
        }

        for (int i = r; i <= H; i++) {
            for (int j = (i == r) ? c : 1; j < N; j++) {
                if (ladder[i][j] == 0 && ladder[i][j + 1] == 0) {
                    ladder[i][j] = 2;
                    ladder[i][j + 1] = 1;
                    dfs(i, j, cnt + 1);
                    ladder[i][j] = ladder[i][j + 1] = 0; // 원상 복구
                }
            }
        }
    }

    // i번의 세로선의 결과가 i번이 나오는지 확인
    private static boolean pass() {
        for (int i = 1; i <= N; i++) {
            int r = 1;
            int c = i;

            for (int j = 1; j <= H; j++) {
                if (ladder[r][c] == 1) {
                    c--;
                } else if (ladder[r][c] == 2) {
                    c++;
                }
                r++;
            }

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

        return true;
    }
}