[백준 15684] 사다리 조작 / 자바 / 브루트포스 + 약간의 구현

#문제         

레벨: G3
알고리즘: 브루트포스 
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 풀이        

난 문제를 볼 때 이것은 규칙이 있나 없나부터 가볍게 생각한다. 딱 떠오르지 않는다면 입출력 제한을 보고 완전탐색인지 확인한다. 이 문제 같은 경우 최대  (10x30)^3 

사다리 구현은 어려울 수 있지만, 굳이 이 문제에서 한가지만 뽑아서 배울 수 있다면, 브루트 포스 문제 풀이 흐름이다.

다리를 놓을 조합을 뽑아놓고(dfs로 구현) 조건에 맞는대로 결과가 나오는지 시뮬레이션 돌린다.

 

---

#풀이 코드      

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

public class Main {
    static int n, m, h; // n: 세로선 개수, m: 가로선 개수, h: 가로선을 놓을 수 있는 위치의 수
    static boolean[][] ladder; // 사다리 상태를 저장하는 2차원 배열
    static int answer = 4; // 최소 가로선 개수 (초기값은 4로 설정, 3보다 큰 경우 -1 출력)

    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][n-1]; // 사다리 배열 초기화

        // 초기 가로선 정보 입력
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            ladder[a][b] = true; // 가로선 위치 표시
        }

        dfs(0, 0, 0); // 깊이 우선 탐색 시작

        // 결과 출력
        System.out.println(answer < 4 ? answer : -1);
    }

    // 현재 사다리 상태가 조건을 만족하는지 확인하는 메서드
    static boolean check() {
        for (int i = 0; i < n; i++) {
            int pos = i; // 시작 위치
            for (int j = 0; j < h; j++) {
                if (pos > 0 && ladder[j][pos-1]) {
                    pos--; // 왼쪽으로 이동
                } else if (pos < n-1 && ladder[j][pos]) {
                    pos++; // 오른쪽으로 이동
                }
            }
            if (pos != i) return false; // 시작 위치와 끝 위치가 다르면 false
        }
        return true; // 모든 세로선이 조건을 만족하면 true
    }

    // 깊이 우선 탐색을 통해 가로선을 추가하는 메서드
    static void dfs(int x, int y, int count) {
        if (count >= answer) return; // 현재까지의 최소값보다 크거나 같으면 탐색 중단
        if (check()) { // 현재 상태가 조건을 만족하면
            answer = Math.min(answer, count); // 최소값 갱신
            return;
        }
        if (count == 3) return; // 가로선 3개를 추가했으면 탐색 중단

        // 가로선 추가 시도
        for (int i = x; i < h; i++) {
            int k = (i == x) ? y : 0; // 같은 높이에서는 이전 위치부터 시작
            for (int j = k; j < n-1; j++) {
                if (ladder[i][j]) continue; // 이미 가로선이 있으면 스킵
                if (j > 0 && ladder[i][j-1]) continue; // 왼쪽에 가로선이 있으면 스킵
                if (j < n-2 && ladder[i][j+1]) continue; // 오른쪽에 가로선이 있으면 스킵

                ladder[i][j] = true; // 가로선 추가
                dfs(i, j+2, count+1); // 다음 위치로 이동하여 재귀 호출
                ladder[i][j] = false; // 가로선 제거 (백트래킹)
            }
        }
    }
}