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

📌문제 링크

---

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

📌문제 설명

---

모든 부분에 가로선을 설치해보면서 백트래킹으로 최소 가로선 개수를 찾아주면 됩니다.

📌코드

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, M, H; // N: 세로선의 개수, M: 가로선의 개수, H: 세로선마다 가로선을 놓을 수 있는 위치의 개수
    static boolean[][] visited; // 가로선이 놓여 있는지 여부를 저장하는 배열
    static int answer = Integer.MAX_VALUE; // 최소 가로선 개수를 저장하는 변수

    public static void main(String[] args) throws Exception {
        input(); // 입력을 받는 메서드 호출
        solve(); // 문제를 해결하는 메서드 호출
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer); // 결과 출력
    }

    // 입력을 받는 메서드
    public static void input() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 세로선의 개수 입력
        M = Integer.parseInt(st.nextToken()); // 가로선의 개수 입력
        H = Integer.parseInt(st.nextToken()); // 세로선마다 가로선을 놓을 수 있는 위치의 개수 입력
        visited = new boolean[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()); // 가로선의 가로 위치
            visited[a][b] = true; // 가로선이 놓여 있음을 표시
        }
        br.close(); // 입력 스트림 닫기
    }

    // 사다리 게임이 정상적으로 동작하는지 확인하는 메서드
    public static boolean checkLadder() {
        for (int start = 1; start <= N; start++) {
            int position = start; // 시작 위치
            for (int row = 1; row <= H; row++) {
                if (position > 1 && visited[row][position - 1]) position--; // 왼쪽으로 이동
                else if (position < N && visited[row][position]) position++; // 오른쪽으로 이동
            }
            if (position != start) return false; // 시작 위치와 다르면 false 반환
        }
        return true; // 모든 시작 위치가 일치하면 true 반환
    }

    // 백트래킹을 이용하여 가로선을 추가하는 메서드
    public static void backTracking(int row, int col, int count) {
        if (count >= answer) return; // 현재 가로선 개수가 최소값 이상이면 종료
        if (checkLadder()) { // 사다리 게임이 정상 동작하면
            answer = Math.min(answer, count); // 최소 가로선 개수 갱신
            return;
        }
        if (count == 3) return; // 가로선 개수가 3개이면 종료

        // 가로선을 추가하는 모든 경우의 수 탐색
        for (int r = row; r <= H; r++) {
            for (int c = (r == row ? col : 1); c < N; c++) {
                if (!visited[r][c] && !visited[r][c - 1]) { // 가로선이 놓여 있지 않으면
                    visited[r][c] = true; // 가로선 추가
                    backTracking(r, c, count + 1); // 재귀 호출
                    visited[r][c] = false; // 가로선 제거
                }
            }
        }
    }

    // 문제를 해결하는 메서드
    public static void solve() {
        backTracking(1, 1, 0); // 백트래킹 시작
    }
}