백준 - 사다리조작(15684)

1. 문제요약

• 사다리게임
• N개의 세로선, M개의 가로선이 있다. 이때 각 가로선에 H개 만큼의 사다리를 놓을 수 있다.
  • 사다리는 서로 인접하거나 연속적일 수 없다.
• i번 세로선의 결과가 i번째로 되기 위해 추가해야 할 최소한의 사다리 수를 구하라.
  • 정답이 3을 초과하거나, 불가능하면 -1 출력

2. 입출력

[입력]

• 세로선 N, 가로선 M, 사다리 개수 H (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)
• 상단부터 가로선의 정보 a b가 차례대로 주어짐
  • a 부터 b까지 연결되는 선이라는 의미

3. 알고리즘

• 세로줄 1~N까지 그리디하게 사다리 표시
• 하나의 재귀에서 출발지 i번째에서 출발 / 도착지 i번째에서 역순 출발을 동시에 한 칸씩 움직임
  • 둘의 높이(i)가 같아지는 순간, j가 1 차이라면, 해당 위치에 사다리 생성
  • 둘의 높이(i)가 같아지는 순간, j가 2 이상의 차이라면, -1 출력
• 알고리즘 반복하며 사다리가 3개를 초과하는 순간 멈추고 -1 출력
• 하나의 세로줄에 사다리를 H개 이상 놓을 시, -1 출력.

• 사다리 표시할 boolean[][] 필요
• 사다리 총합 나타낼 int[] 필요 -> H개 초과 시 즉시 종료 위함

=> 그러나.. 당연히 위와 아래를 동시 탐색해서 사다리를 설치하는 방식은, 결국 중간에만 다리를 설치할 수 있기에 불가능한 로직이었음

4. 정답 알고리즘

• 브루트포스, 백트래킹 활용!
• 첫 번째 수직선부터 마지막 수직선까지 차례대로 모든 경우의 수 탐색. 조건 만족 케이스 나올 시 바로 종료
  • 사다리는 최대 3개 놓을 수 있으니, 1개 놓기 / 2개 놓기 / 3개 놓기 의 경우도 모두 탐색.
    • 사다리는 이미 놓여진 곳 / 각 양쪽 끝자리 가 아닐 시 놓을 수 있음.
  • 원하는 개수만큼 놓았을 시 모든 i 번째 출발지가 i 번째 도착하는지 확인

재귀에서 가장 중요한 건, 종료조건 설정!!!

해당 유형 문제를 풀 때는 종료조건 설정 -> 큰 틀 잡기 -> 예외처리 순서대로 진행해보자.

생각보다 내가 큰 틀 잡기에 집중하느라 이걸 놓치는 것 같다.

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

public class Main {

    static int N;          // 세로선 개수
    static int M;          // 기존 가로선 개수
    static int H;          // 가로선 높이 개수
    static boolean[][] hasBridge;   // hasBridge[row][col] : row 높이에서 col과 col+1 연결 여부
    static int answer = -1;

    public static void main(String[] args) throws Exception {

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

        hasBridge = new boolean[H + 1][N + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken());   // 높이
            int col = Integer.parseInt(st.nextToken());   // 세로선 번호
            hasBridge[row][col] = true;
        }

        // 0~3개 추가 시도
        for (int maxAdd = 0; maxAdd <= 3; maxAdd++) {
            if (dfs(0, maxAdd)) {
                answer = maxAdd;
                break;
            }
        }

        System.out.println(answer);
    }

    static boolean dfs(int addedCount, int maxAdd) {

        if (addedCount == maxAdd) {
            return isValidLadder();
        }

        for (int row = 1; row <= H; row++) {
            for (int col = 1; col < N; col++) {

                if (hasBridge[row][col]) continue;

                // 왼쪽 인접 체크
                if (col > 1 && hasBridge[row][col - 1]) continue;

                // 오른쪽 인접 체크
                if (col < N - 1 && hasBridge[row][col + 1]) continue;

                hasBridge[row][col] = true;

                if (dfs(addedCount + 1, maxAdd)) return true;

                hasBridge[row][col] = false;
            }
        }

        return false;
    }

    static boolean isValidLadder() {

        for (int startLine = 1; startLine <= N; startLine++) {

            int currentLine = startLine;

            for (int row = 1; row <= H; row++) {

                if (currentLine < N && hasBridge[row][currentLine]) {
                    currentLine++;
                }
                else if (currentLine > 1 && hasBridge[row][currentLine - 1]) {
                    currentLine--;
                }
            }

            if (currentLine != startLine) return false;
        }

        return true;
    }
}