[백준 15684번] 사다리 조작 :: 늦깎이 IT

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

1. 사다리를 생성하기 위해 가로선을 입력받는 형태(?)를 살펴보자.

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

- 즉, 입력으로 받는 a는 가로선이 추가될 행이고, b는 b+1 세로선과 연결되는 열이다.

- 만약, map[0][0]이 1이라면, [0][0]과 [0][1] 사이에 가로선이 있다는 뜻이다.

2. 사다리 그림을 2차원 배열로 나타내본다. 아래의 사다리의 연결 형태를 보면

1) map[1][1] ↔ map[1][2]

2) map[2][3] ↔ map[2][4]

3) map[3][2] ↔ map[3][3]

4) map[5][1] ↔ map[5][2]

5) map[5][4] ↔ map[5][5]

와 같이 연결되어 있다. 2차원 배열에서는 빨간색으로 표시된 map의 좌표에만 1을 표시한다. 

3. 입력으로 주어지는 사다리를 모두 표시했으면, 이제 임의의 자리에 사다리를 놔야한다. 사다리는 DFS 탐색으로 진행하며 문제에서 설명했듰이 설치된 사다리의 갯수가 3보다 클 경우에는 탐색을 멈춘다. 사다리를 놓는 과정은 다음과 같다.

1) 현재 위치의 값이 0인지 확인한다. (0은 빈칸)

2) 0이라면, 그 위치의 왼쪽과 오른쪽에 사다리가 설치되어 있는지 확인한다. (isPossible() 메소드 참조)

3) 왼쪽, 오른쪽에 사다리가 설치되어 있지 않다면 해당 위치에 사다리를 설치한다.

4) 1)으로 돌아가 반복한다.

4. 사다리 게임을 시작한다. 사다리를 하나씩 설치할 때 마다 사다리 게임이 성공하는지 확인한다.

1) 해당 위치가 1인 경우

 - 그 위치에서 오른쪽으로 사다리가 연결되어 있다는 뜻이므로, 오른쪽으로 이동한다.

2) 해당 위치가 0인 경우

 - 그 위치에서 오른쪽으로 연결된 사다리는 없지만, 왼쪽 사다리가 존재할 수 있다.

 - 따라서, 해당 위치에서 왼쪽 값이 1인지 확인하고, 1이라면 왼쪽으로 이동, 0이라면 아래쪽으로 이동한다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int N, H, M, ans = Integer.MAX_VALUE;
    public static int[][] map;
    public static boolean success = false;
    public static int[] dirX = new int[] { -1, 0, 1, 0 }; // 북 동 남 서
    public static int[] dirY = new int[] { 0, 1, 0, -1 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
 
        map = new int[H][N];
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a - 1][b - 1] = 1;
        }
        dfs(0, 0);
        if (ans == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(ans);
    }
 
    public static void dfs(int start, int ladder) {
 
        if (ladder > 3 || ladder >= ans)
            return;
 
        if (descendLadder()) {
            ans = Math.min(ans, ladder);
            success = true;
            return;
        }
 
        for (int i = start; i < H * N; i++) {
 
            int row = i / N;
            int col = i % N;
 
            if (col == N - 1)
                continue;
 
            if (map[row][col] == 0 && isPossible(row, col)) {
                map[row][col] = 1;
                dfs(i + 1, ladder + 1);
                map[row][col] = 0;
            }
        }
    }
 
    public static boolean descendLadder() {
 
        for (int i = 0; i < N; i++) {
 
            int col = i;
 
            for (int j = 0; j < H; j++) {
 
                if (map[j][col] == 1) {
                    col += 1;
                } else if (isBoundary(j, col - 1) && map[j][col - 1] == 1) {
                    col -= 1;
                }
            }
            if (col != i)
                return false;
        }
        return true;
    }
 
    public static boolean isPossible(int row, int col) {
 
        if (isBoundary(row, col + 1) && map[row][col + 1] == 1)
            return false;
 
        if (isBoundary(row, col - 1) && map[row][col - 1] == 1)
            return false;
 
        return true;
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < H) && (col >= 0 && col < N);
    }
 
    public static void showMap(int[][] map) {
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}Colored by Col