[BOJ] 백준 15684 사다리 조작

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 

5 5 6

1 1

3 2

2 3

5 1

5 4

 

 Output 

3

세로선 N개와 가로선이 놓일 수 있는 점선 H와

점선 구간에 놓여져 있는 M개의 가로선 정보가 주어집니다.

※ (a, b) = a번째 점선 위치에서 b ~ b+1 세로선을 연결

 

사다리 진행 방식

i 번째 세로선(Col)에서 출발 했으면 동일한 i 번째 세로선(Col)에 도착하게 하는

최소 가로선의 추가 개수를 출력하는 문제입니다. 

※ 추가 가로선 인접한 두 세로선을 연결.

* 두 가로선이 연속하거나 서로 접해서는 안됩니다.

 

 

가로선을 3개 놓아서 i번째 세로선의 결과가 i가 되었습니다.

* 만약 추가 가로선 개수가 4개 이상 필요하면 『-1』 출력

* 불가능한 경우에도 『-1』 출력

 

구현

최대 3개 추가 가로선을 놓을 수 있는 경우를 완전탐색 합니다.

또한, 가로선이 연속하거나 서로 접하지 않기에

위의 O 지점에서 왼쪽으로 갈지 오른쪽으로 갈지에 대한 처리가 필요 없습니다.

- 이차원 배열을 이용하여 사다리 구현

* 가로선을 왼쪽 → 오른쪽으로 긋는 방식으로 구현 

* 실제 사다리를 타고 내려갈 때, 아래 방식으로 이동

   『1』: 오른쪽으로 이동 / 『2』: 경우 왼쪽으로 이동

 

- 가로선을 놓을 수 있는 곳 →  0~3개까지 추가 가로 사다리 경우의 수 구하기.

Q. 처음 주어진 사다리에서 추가로 사다리를 놓을 수 없는 공간은 어디일까?

A. 바로 특정 가로선이 놓여져 있지 않은 좌우 공간이다. 

     (문제 조건) 연속하거나 접해서는 안된다

    이는 추가로 가로선을 놓았을 경우 놓은 자리의 좌우도 마찬가지다.

    그렇기에 가로선을 추가할 때마다 좌우에 놓지 못하도록 설정해야 합니다.

 

[추가 가로선 3개를 놓을 때, 놓을 수 있는 위치]

▶ 5개의 　　의 영역 중 인접하거나 연속되지 않아야 하므로 가로선 놓일 수 있는 경우는 7 곳이며,

     그 중 3가지 놓는 곳을 탐색해야 합니다. → 제한이 있는 조합Combination

      (결국, 추가 가로선이 놓일 수 있는 곳은 이차원 배열 원소값이 0인 곳.)

 

추가 가로선을 놓은 후, 『 i 』 열에서 출발하여 『 i 』열로 도착하는지 확인

* 추가 가로선 개수가 최소값을 구하는 것이므로 중간에 만족하면 종료.

    ~ 가로선 0개 놓을 수 있는 모든 경우의 수

    ~ 가로선 1개 놓을 수 있는 모든 경우의 수

    ~ 가로선 2개 놓을 수 있는 모든 경우의 수

    ~ 가로선 3개 놓을 수 있는 모든 경우의 수

 

(참고) 문제에서 요구하는 i 번째의 결과가 i가 나오기 위해서는

          기존 + 추가 가로선의 총 개수가 짝수여야 합니다.

ex) 5번째 세로선에서 좌측으로 빠지는 가로선이 한개 있으면

      5번째 세로선으로 돌아올 수 없기 때문입니다.

---

import java.util.Scanner;

public class Main {
    
    static int[][] board;
    static int N, M, H;
    static int maxPlusBridge;
    static int answer = -1;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 열의 개수
        N = Integer.parseInt(sc.next());
        // 초기에 놓여진 사다리 개수
        M = Integer.parseInt(sc.next());
        // 행의 개수
        H = Integer.parseInt(sc.next());
        
        // 1행 1열로 시작하기 위한 인덱스 조정
        board = new int[H+1][N+1];
        
        for(int i=0; i<M; i++) {
            int x = Integer.parseInt(sc.next());
            int y = Integer.parseInt(sc.next());
            // (x,y)에서 (x,y+1) 좌표로 오른쪽으로 이동하는 의미로 '1'
            // (x,y+1)에서 (x,y) 좌표로 왼쪽으로 이동하는 의미로 '2'
            board[x][y] = 1; board[x][y+1] = 2;
        }
        // 추가 가로선 0 ~ 3개 Case 별로 구하기
        for(maxPlusBridge=0; maxPlusBridge<=3; maxPlusBridge++) {
            // 탐색 과정에서 만족한다면 종료
            if(answer != -1) break;
            DFS(1, 1, 0);
        }
        
        System.out.println(answer);
    }




    private static void DFS(int x, int y, int bridgeCnt) {
        // 탐색 과정에서 만족한다면 종료
        if(answer != -1) return;
        
        if(bridgeCnt >= maxPlusBridge) {
            if( isOK() ) answer = bridgeCnt;
            return;
        }

        int j = y;
        for(int i=x; i<=H; i++) {
            while(true) {
                // 왼쪽에서 오른쪽으로 긋기 때문에 마지막 열 앞에까지만 확인
                if(j >= N) {
                    j = 0;
                    break;
                }
                // 사다리를 놓을 수 있는지 확인(연속하거나 인접하지 않도록)
                if(board[i][j] == 0 && board[i][j+1] == 0) {
                    // 해당 구간에 추가 가로선 긋기
                    board[i][j] = 1; board[i][j+1] = 2;
                    DFS(i, j, bridgeCnt + 1);
                    // 해당 구간을 긋지 않고 Skip
                    board[i][j] = 0; board[i][j+1] = 0;
                }
                j++;
            }            
        }
    }


    private static boolean isOK() {
        // 각 열을 출발점으로 시작
        for(int startY=1; startY<=N; startY++) {
            int y = startY;
            // 한 칸씩 아래로 이동
            for(int x=1; x<=H; x++) {
                switch (board[x][y]) {
                // 우측으로 이동
                case 1:
                    y += 1;
                    break;
                // 좌측으로 이동
                case 2:
                    y -= 1;
                    break;
                // 사다리가 없는 경우 (0)
                default:
                    break;
                }
            }
            // 끝지점에 도착했을 출발 했을 때의 세로선상이 동일한지 확인
            if(y != startY) return false;
        }
        return true;
    }
}