백준 사다리 조작

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N - 1) × H)
둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.
가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N - 1) b번 세로선과 b + 1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.
가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다.
세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.
입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다.
만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

내가 이 문제를 보고 생각해본 부분

입력 및 변수 선언
N, M, H를 입력받아 초기화한다.
ladder 2차원 boolean 배열을 만들어서 ladder[a][b]가 true이면 a번째 위치에서 b번째 세로선과 b + 1번째 세로선 사이에 가로선이 있음을 뜻한다.
기존 가로선 정보 저장
입력에서 주어진 가로선 위치를 ladder 배열에 저장한다.
사다리 게임 종료 위치 검사 함수 check()
모든 세로선 i에 대해, 1부터 H까지 내려가며 가로선을 만나면 옆 세로선으로 이동한다.
결과적으로 아래까지 왔을 때 각 출발 세로선과 도착 위치가 같으면 성공이다.
DFS 백트래킹 함수 dfs()
현재까지 추가한 가로선 개수 cnt, 탐색 시작 위치 (x, y)를 받는다.
cnt가 현재 answer (최소값) 이상이면 종료한다.
check()가 성립하면 answer를 최소화하고 종료한다.
최대 추가 3개까지만 시도하고, 3개 초과는 중단한다.
가능한 모든 위치에 가로선을 놓으면서 다음 탐색을 재귀 호출한다.
가로선은 서로 인접하거나 기존 가로선과 붙어있으면 안되므로, 좌우 모두 비어있는지 확인한다.
최종 출력
answer가 초기 값 4 그대로면 불가능하여 -1 출력, 아니면 최소 개수 출력한다.

코드로 구현

package baekjoon.baekjoon_33;

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

// 백준 15684번 문제
public class Main1336 {
    static int N, M, H;
    static boolean[][] ladder; // ladder[a][b] = a번째 줄, b번째 세로선과 b+1번째 세로선 사이 가로선 존재 여부
    static int answer = 4; // 최소 개수 저장, 3보다 크면 불가능

    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 boolean[H + 1][N + 1]; // 1-based index 사용

        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] = true;
        }

        dfs(0, 1, 1);
        System.out.println(answer == 4 ? -1 : answer);
        br.close();
    }

    // 각 세로선이 자기 자신으로 끝나는지 체크
    static boolean check() {
        for (int i = 1; i <= N; i++) {
            int pos = i;
            for (int j = 1; j <= H; j++) {
                if (ladder[j][pos])
                    pos++;        // 오른쪽으로 이동
                else if (pos > 1 && ladder[j][pos - 1])
                    pos--;  // 왼쪽으로 이동
            }
            if (pos != i)
                return false; // 위치가 원래 세로선 번호와 다른 경우 실패
        }
        return true;
    }

    // 깊이 우선 탐색으로 가로선 추가 시도
    // cnt: 추가한 가로선 개수, x: 시작 행, y: 시작 열
    static void dfs(int cnt, int x, int y) {
        if (cnt >= answer)
            return; // 이미 더 큰 개수 시도는 의미 없음
        if (check()) {
            answer = cnt;
            return;
        }
        if (cnt == 3)
            return; // 3개 초과 불가

        for (int i = x; i <= H; i++, y = 1) {  // i는 행 (위에서 아래)
            for (int j = y; j < N; j++) {       // j는 세로선 위치
                if (!ladder[i][j] && !ladder[i][j - 1] && !ladder[i][j + 1]) {
                    ladder[i][j] = true;
                    dfs(cnt + 1, i, j + 2); // 다음부터 이어서 탐색 (j+2로 중복방지)
                    ladder[i][j] = false;
                }
            }
        }
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.