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

[백준 15684] 사다리 조작 : https://www.acmicpc.net/problem/15684

---

문제 조건 정리

 

1. 사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다.
2. 이때, i번 세로선의 결과가 i번이 나와야 한다.
   그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

---

입력 / 출력 정리

 

1. 첫째 줄에
   세로선의 개수 N (2 ≤ N ≤ 10),
   가로선의 개수 M (0 ≤ M ≤ (N-1)×H),
   세로선마다 가로선을 놓을 수 있는 위치의 개수 H (1 ≤ H ≤ 30)가 주어진다.
   
   
2. 둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.
   가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1)
   b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.
   -> 세로선(N)은 이동할 수 있는 선의 개수
   -> 세로선과 세로선 사이의 개수는 (N-1)
   -> 배열의 사이즈 = 행 * 열 = 가로선의 개수(H) * 세로선의 개수(N-1)
   -> [H][N-1]
   
   
3. 가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다.
   세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.
   -> 배열의 인덱스는 1에서 시작
   -> [H+1][N]
   
   
4. 입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.
   -> 가로 이동은 1회 이하로 연속되지 않음, 가로선을 추가할 때 사용해야 할 조건
   
   
5. i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다.
   만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.
   -> 조건: 1번 세로선의 결과는 1번, 2번 세로선의 결과는 2번, ...
   -> 가로선을 추가하지 않았을 때, 가로선을 1개 ~ 3개 추가했을 때의 결과를 알아본다.
   -> 조건을 만족한다면 더 이상 진행하지 않고 정답을 출력한다.
   -> 조건을 만족하지 못한다면 (정답이 3보다 크거나 불가능한 경우) -1 출력

---

문제를 풀어보며

 

1. 사다리를 어떻게 배열에 나타낼지 고민함.
   결국엔 사다리의 위치만 boolean 배열로 표현함.
   
   
2. 배열의 가로 세로를 관리하는 게 너무 헷갈렸음.
   이런 문제가 가끔 있던데 의도적이라고 생각함... 계속 배열의 가로축, 세로축을 되새기며 풀이를 진행했음.
   
   
3. 가로선을 추가하지 않는 경우부터, 가로선을 3개 추가하는 경우를 위해서,
   재귀 호출의 시작을 4회(0, 1, 2, 3) 진행함.
   
   
4. 이중반복문에서 백트래킹을 진행하는 경우, 즉 이중 반복문에서 가로선을 선택하는 경우
   재귀 호출의 파라미터가 반복문을 관리하는 인덱스가 된다.
   이때, 내부 반복문의 인덱스를 올바르게 관리하기 위해서 삼항연산을 사용했다.

// 간단한 예시
fun boolean simulate(int depth, int sRow, int sCol, int limit) {
    for (int i = sRow; i <= h; i++) {
        for (int j = (i == sRow ? sCol : 1); j < n; j++) {
           simulate(depth + 1, i, j + 1, limit)
           }
      }
}

 

 

---

코드

 

package baekJoon;

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

public class BJ15684 {
    static int n, m, h;

    static boolean[][] hMap;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
        n = Integer.parseInt(stringTokenizer.nextToken()); // 세로 축 개수
        m = Integer.parseInt(stringTokenizer.nextToken()); // 기존의 가로 선 개수
        h = Integer.parseInt(stringTokenizer.nextToken()); // 가로 축 개수 (점선 축 개수)
        if (m == 0) {
            System.out.println(0);
            return;
        }

        // row: 1~h
        // col: 1~(n-1)
        hMap = new boolean[h + 1][n];

        for (int i = 0; i < m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            int row = Integer.parseInt(stringTokenizer.nextToken());
            int col = Integer.parseInt(stringTokenizer.nextToken());

            // row 행의
            // col 열과 col+1 열이 연결됨
            hMap[row][col] = true;
        }

        // 추가되는 선의 개수를 제한 (0, 1, 2, 3)
        for (int limit = 0; limit <= 3; limit++) {
            // *** true 반환받으면 즉시 종료 ***
            if (simulate(0, 1, 1, limit)) {
                System.out.println(limit);
                return;
            }
        }

        // 0, 1, 2, 3 으로 해결하지 못한다면
        System.out.println(-1);

    }

    private static boolean simulate(int depth, int sRow, int sCol, int limit) {
        // 추가된 가로선의 개수가 제한한 개수와 같다면
        // i번에서 출발해서 i번으로 도착하는지 확인
        if (depth == limit) {
            // check 의 반환에 따라서
            // 실패 --> false 반환
            // 성공 --> true 반환
            // *** 반환을 받기 위해서 호출을 조건으로 감싸야함 ***
            return check();
        }

        for (int i = sRow; i <= h; i++) {
            for (int j = (i == sRow ? sCol : 1); j < n; j++) {
                // 이미 사다리가 있는 자리는 사다리 설치 불가
                if (hMap[i][j]) continue; 
                
                // 배열 범위 검사 이후,
                // 내 왼쪽에 사다리가 있으면 사다리 설치 불가
                if (1 < j && hMap[i][j - 1]) continue;

                // 배열 범위 검사 이후,
                // 내 오른쪽에 사다리가 있다면 사다리 설치 불가
                if (j < n - 1 && hMap[i][j + 1]) continue;

                // 정상적으로 설치
                hMap[i][j] = true;
                
                // *** true 반환받으면 즉시 종료 ***
                if (simulate(depth + 1, i, j + 1, limit)) {
                    return true;
                }
                
                // 위 반환이 false 였다면, 백트래킹 (사다리 설치한거 없애기)
                hMap[i][j] = false;
            }
        }

        return false;
    }

    private static boolean check() {
        // 1번 세로축부터 n번 세로축까지 확인
        for (int start = 1; start <= n; start++) {

            // 시작 세로축(열)
            int col = start;

            // 시작 가로축 = 1, 도착 가로축 = h
            for (int row = 1; row <= h; row++) {
                // 배열 범위 검사 이후,
                // 현재 오른쪽으로 이동 가능한 사다리가 있다면
                if (col < n && hMap[row][col]) {
                    col++;
                }
                
                // 배열 범위 검사 이후,
                // 현재 왼쪽으로 이동 가능한 사다리가 있다면
                else if (col > 1 && hMap[row][col - 1]) {
                    col--;
                }
            }

            // 시작점과 도착점이 같지 않다면 즉시 실패로 종료
            if (start != col) {
                return false;
            }
        }

        // n번의 반복이 정상적으로 진행되었다면 성공
        return true;
    }

    // 테스트용 출력
    private static void printMap() {
        for (int i = 1; i < hMap.length; i++) {
            for (int j = 1; j < hMap[0].length; j++) {
                System.out.print(" | " + (hMap[i][j] ? "--" : "  "));

            }
            System.out.print(" | ");
            System.out.println();
        }
        System.out.println();
        System.out.println();
    }
}

 

---

문제를 풀고 난 후

 

배열 인덱스 관리가 어려운 문제는 역시 커피 한잔 마시고 풀어야 한다.

 

헷갈렸던 부분은 주석으로도 강조해 뒀지만,
boolean 타입을 반환하는 재귀 함수는 첫 호출과 함수 내에서의 n번째 호출에서 반환을 받을 수 있는 환경을 마련해야 한다는 것이다.

이를 활용해서 효율적으로 문제를 해결할 수 있었다.

 

boolean 타입의 재귀 함수는 익숙하지 않아서 좋은 학습이었다.