[백준] 15684 - 사다리 조작 문제 풀이 (백트래킹)

문제 소개

오늘 풀었던 백준 15684번 - 사다리 조작 문제를 정리합니다.

이 문제는 사다리를 조작하여 특정 조건을 만족시키는지 확인해야 하는 백트래킹 유형의 문제입니다.

문제의 핵심은 "추가할 수 있는 사다리의 개수 제한(3개)"과 "조건을 만족하는 최소 사다리 개수"를 찾는 데 있었습니다.

문제 링크: 사다리 조작 - 백준 15684번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 백트래킹을 이용하여 사다리를 추가하면서 조건을 만족하는지 확인.
2. 조건을 만족하는 최소 사다리 개수를 찾되, 3개를 초과할 경우 -1을 반환.
3. 사다리의 유효성을 확인하는 함수를 구현하여 모든 사다리가 제대로 연결되었는지 확인.

---

해결 과정 및 코드

핵심 아이디어

1. 사다리를 최대 3개까지 추가할 수 있으므로, 추가 개수를 제한하여 DFS 탐색.
2. 사다리를 추가할 때, 연속된 위치에 추가할 수 없도록 조건 설정.
3. 사다리가 올바르게 연결되었는지 확인하는 검증 함수 사용.

코드

시간 복잡도 : 최대 O(N^3) (모든 칸에 대해 DFS 탐색)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = read(); // 세로선 개수
        int M = read(); // 기존 가로선 개수
        int H = read(); // 가로선을 놓을 수 있는 위치 개수

        // 사다리 정보를 저장할 2차원 배열
        boolean [][] ladder = new boolean[H + 1][N + 1];

        // 기존 가로선 정보 입력
        for (int m = 0; m < M; m++) {
            int a = read(); // 가로 위치 
            int b = read(); // 시작한 세로 위치
            ladder[a][b] = true;
        }

        bw.write(Integer.toString(solve(N, H, M, ladder)));
        bw.flush();
    }

    private static int solve(int n, int h, int m, boolean[][] ladder) {
        // 기존에 홀수 개의 가로선이 있는 세로선이 3개 초과라면 불가능
        // 홀수 개 칸에 +1 가로선을 해야함 => 정답이 3보다 큼
        if (countOddLines(ladder, n, h) > 3) {
            return -1;
        }

        // 추가할 가로선 개수를 0, 1, 2, 3 순으로 시도
        // 기존 가로선이 홀수 개라면 홀수 개 추가 / 짝수 개면 최대 짝수 개 추가
        for (int limit = m % 2; limit < 4; limit += 2) {
            if (tryAddLadders(n, h, ladder, limit)) {
                return limit;
            }
        }
        return -1; // 3개 이내로 해결할 수 없으면 -1 반환
    }

    private static int countOddLines(boolean[][] ladder, int n, int h) {
        int oddCount = 0;
        for (int x = 1; x < n; x++) { // 각 세로선을 순회
            boolean isOdd = false;
            for (int y = 1; y <= h; y++) { // 해당 세로선의 모든 가로선을 확인
                if (ladder[y][x]) isOdd = !isOdd; // 가로선이 있으면 홀수 상태 반전
            }
            if (isOdd) oddCount++; // 홀수 개의 가로선이 있으면 카운트 증가
        }
        return oddCount;
    }

    private static boolean tryAddLadders(int n, int h, boolean[][] ladder, int limit) {
        // DFS로 가로선을 추가하며 조건을 만족할 수 있는지 확인
        return dfs(n, h, 1, 1, 0, limit, ladder);
    }

    private static boolean dfs(int n, int h, int y, int x, int count, int limit, boolean[][] ladder) {
        // 추가한 가로선 개수가 목표(limit)에 도달했으면 유효성 검사
        if (count == limit) return validateLadders(n, h, ladder);

        // 현재 줄(y)에서 이후로 가로선을 추가
        for (int nx = x; nx < n; nx++) {
            if (addLadderAndCheck(n, h, y, nx, count, limit, ladder)) return true;
        }

        // 다음 줄(y+1)에서 가로선을 추가
        for (int ny = y + 1; ny <= h; ny++) {
            for (int nx = 1; nx < n; nx++) {
                if (addLadderAndCheck(n, h, ny, nx, count, limit, ladder)) return true;
            }
        }

        return false; // 조건을 만족할 수 없으면 false 반환
    }

    private static boolean addLadderAndCheck(int n, int h, int y, int x, int count, int limit, boolean[][] ladder) {
        // 가로선을 추가할 수 있는지 확인 (연속된 가로선이 없어야 함)
        if (ladder[y][x] || ladder[y][x - 1] || ladder[y][x + 1]) {
            return false;
        }

        ladder[y][x] = true;
        // DFS로 추가 후 조건 만족 여부 확인
        boolean result = dfs(n, h, y, x, count + 1, limit, ladder);
        // 가로선 제거 (백트래킹)
        ladder[y][x] = false;

        return result;
    }

    // 모든 세로선이 자기 자신으로 연결되는지 확인
    private static boolean validateLadders(int n, int h, boolean[][] ladder) {
        for (int x = 1; x <= n; x++) {
            int current = x; // 시작 세로선 번호
            for (int y = 1; y <= h; y++) {
                if (ladder[y][current]) { // 오른쪽으로 이동
                    current++;
                } else if (current > 1 && ladder[y][current - 1]) { // 왼쪽으로 이동
                    current--;
                }
            }
            if (current != x) {
                return false;
            }
        }
        return true;
    }

    static int read() throws Exception {
        int n = System.in.read() & 15, cur;
        while ((cur = System.in.read()) > 32) {
            n = (n << 3) + (n << 1) + (cur & 15);
        }
        return n;
    }