[백준] 15684 사다리 조작 (JAVA)

문제 링크:

15684번: 사다리 조작

 

 

난이도 : 골드 3

 

 

문제:

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

 

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

 

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

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

 

 

입력:

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

 

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

 

가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.

 

입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

 

 

출력:

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

 

 

 

 

문제 이해:

작성자는 처음 이 문제를 접했을 때 문제 자체를 이해하는 데에도 시간이 오래 걸렸다.

첫 번째 입력 줄에서 N M H가 주어진다.

• N은 세로 줄의 개수,
• M은 이미 놓여 있는 가로선(사다리 연결)의 개수,
• H는 가로선을 놓을 수 있는 높이(행의 개수)를 의미한다. 예를 들어, 힌트 예제 3을 보면 행이 6줄인 것을 확인할 수 있는데, 이것이 바로 H 값이다.

이후 두 번째 줄부터는 가로선의 위치가 주어진다.
예를 들어, 1 1이 입력되었다면 1번째 행에서 1번 세로줄과 2번 세로줄이 연결되어 있다는 뜻이다.
또 3 2라면 3번째 행에서 2번 세로줄과 3번 세로줄이 연결되어 있다는 의미이다.

 

이제 입력 형식은 이해가 되었을 것이다.

 

문제의 핵심은 가로선을 최소한으로 추가 배치하여(이때 사다리가 겹치거나 연속되면 안된다), 1번 세로줄의 결과가 1번, 2번 세로줄의 결과가 2번, … 이런 식으로 모든 세로줄의 시작 인덱스와 도착 인덱스가 동일해지도록 만드는 것이다. 단, 가로선을 3개보다 많이 추가해야 한다면 불가능한 경우로 판단하여 -1을 출력한다.

즉, 예제 3의 정답처럼 파란 가로선을 3개 추가로 배치하면, 모든 출발 인덱스가 도착 인덱스와 일치하게 된다.

 

 

구현 방향:

작성자는 문제를 이해한 직후, 해결 방법으로 브루트포스와 백트래킹 방식을 떠올렸다.
이 문제의 핵심은 가능한 모든 위치에 가로선을 배치해 보면서 조건을 만족하는지 확인하는 것이다. 하지만 단순히 무작정 모든 경우를 시도하는 것은 비효율적이기 때문에, 탐색 과정에서 의미 없는 경우를 일찍 배제할 수 있는 전략이 필요하다.

 

먼저, 기본적인 아이디어는 다음과 같다.
가능한 모든 위치를 순서대로 탐색하면서 “이 자리에 가로선을 놓을 것인지, 놓지 않을 것인지”를 선택한다. 이렇게 하면 자연스럽게 모든 경우의 수를 확인할 수 있다. 하지만 경우의 수가 매우 많아질 수 있으므로, 탐색 도중 더 이상 해답이 될 수 없는 상황이라면 곧바로 되돌아가는 백트래킹을 적용한다. 예를 들어, 이미 세 개 이상의 가로선을 추가한 경우에는 더 이상 진행할 필요가 없으므로 즉시 탐색을 중단한다.

 

또한, 가로선을 추가할 때는 몇 가지 제약 조건이 따른다. 같은 위치에 이미 가로선이 놓여 있거나, 양옆에 가로선이 존재하는 경우에는 새로운 가로선을 놓을 수 없다. 이런 조건들을 사전에 검사해 불가능한 경우를 제외함으로써 불필요한 탐색을 줄일 수 있다.

 

정리하면, 이 풀이 방식은 모든 경우를 고려하는 완전탐색의 형태를 유지하면서도,

• 가지치기를 통해 불필요한 경우는 빠르게 배제하고,
• 조건을 만족하지 않으면 재귀적으로 더 깊이 탐색하는 방식으로 문제를 해결한다.

이러한 접근을 통해, 작성자는 제한 조건(사다리를 최대 3개까지만 추가) 안에서 올바른 해답을 도출할 수 있도록 구현하였다.

 

 

정답 코드:

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

public class Main {
    static int N,M,H;
    static boolean [][]matrix;
    static int min= Integer.MAX_VALUE;

    /**
     * 사다리게임
     * 모든 시작점들 결과가 마지막 시점이랑 일치하는지검사
     */
    public static boolean game() {
        for(int i=0; i<N; i++) {
            int pos = i;
            for (int h = 0; h < H; h++) {
                if (pos < N-1 && matrix[h][pos]) {
                    // 오른쪽 이동
                    pos++;
                } else if (pos > 0 && matrix[h][pos - 1]) {
                    // 왼쪽 이동
                    pos--;
                }
                // else: 그냥 아래로 이동
            }
            if(pos!=i){
                return false;
            }
        }
        return true;
    }

    public static void solve(int num ,int height,int addCount){

        if (addCount >= min || addCount > 3) return;

        // 모든 위치를 다 훑었으면 여기서 판정
        if (height == H) {
            if (game()) min = Math.min(min, addCount);
            return;
        }

        //  먼저 "안 놓고 진행"
        if (num == N - 1) solve(0, height + 1, addCount);
        else solve(num + 1, height, addCount);

        // 가로선을 추가할 수 없는 경우 → 이미 '안 놓고' 진행했으니 더 탐색하지 않고 종료
        if ( (matrix[height][num])
                || num == N - 1
                || (num > 0 && matrix[height][num - 1])
                || (num < N - 1 && matrix[height][num + 1]) ) {
            return;
        }

        // 가로선을 추가할 수 있는 경우 (놓고 진행)
        matrix[height][num] = true;
        if (num == N - 1) solve(0, height + 1, addCount + 1);
        else solve(num + 1, height, addCount + 1);
        matrix[height][num] = false;
    }


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

        matrix = new boolean[H][N]; //높이, 세로선 부 확인 로직

        //가로선 추가
        for (int i = 0; i < M; i++) {
            int height, connect;
            st = new StringTokenizer(br.readLine());
            height = Integer.parseInt(st.nextToken());
            connect = Integer.parseInt(st.nextToken());
            matrix[height - 1][connect - 1] = true;
        }

        //초기 세팅 끝

        //탐색 시작
        solve(0, 0, 0);


        //결과 출력
        if (min == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(min);


    }

}

 

 

마무리하며:

작성자는 처음에 “놓을 수 있으면 바로 놓고 탐색을 시작하는 방식”으로 구현했기 때문에, 가로선을 놓지 않아야 최적의 해가 나오는 경우를 놓쳐 버렸다. 그 결과, 가능한 모든 해를 제대로 탐색하지 못하는 문제가 발생했다.

 

이후 블로그 글을 참고하여 방식을 수정하였다. 먼저 아무 가로선도 추가하지 않은 채 끝까지 탐색을 진행한 뒤, 백트래킹을 하면서 가로선을 추가하는 방식으로 구현을 바꾸었다. 이를 통해 모든 경우의 수를 빠짐없이 고려할 수 있었고, 결국 문제를 올바르게 해결할 수 있었다.

 

 

감사합니다.