BOJ 14923 미로 탈출

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

문제

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

---

입력

N M
Hx Hy
Ex Ey
N X M 행렬

• 2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000
• 1 ≤ Hx, Hy, Ex, Ey ≤ 1000
• (Hx, Hy)≠ (Ex, Ey)
• 행렬은 0과 1로만 이루어져 있고, 0이 빈 칸, 1이 벽이다.

---

출력

D (탈출 할 수 없다면, -1을 출력한다.)

---

예제 입력 1

5 6
1 1
5 6
0 1 1 1 0 0
0 1 1 0 0 0
0 1 0 0 1 0
0 1 0 0 1 0
0 0 0 1 1 0

예제 출력 1

11

---

힌트

제일 왼쪽 위 위치에서 제일 오른쪽 아래 위치로 이동하려면 (3,2) 벽을 파괴하고 이동하면 된다.

---

코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    // 큐에 저장할 정보
    static class Progress {
        int row, col, usedMagic;

        public Progress(int row, int col, int usedMagic) {
            this.row = row;
            this.col = col;
            this.usedMagic = usedMagic;
        }
    }
    static int N, M;
    static int[][] map;
    static boolean[][][] visited;
    static int[] dirRow = {-1, 0, 0, 1}, dirCol = {0, 1, -1, 0};
    static final int LIMIT_MAGIC = 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());
        map = new int[N][M];

        // 방문 여부 확인을 위한 3차원 배열
        // 마법을 1번까지만 사용할 수 있기 때문에 마법을 사용하지 않았을 때와 마법을 사용했을 때 두 가지를 체크해야 한다.
        visited = new boolean[N][M][LIMIT_MAGIC + 1];

        Queue<Progress> queue = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        // 시작점을 입력받아 큐에 offer 하고 방문 처리한다.
        Progress start = new Progress(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1, 0);
        visited[start.row][start.col][0] = true;
        queue.offer(start);

        // 탈출 위치를 입력받는다.
        Point goal = new Point();
        st = new StringTokenizer(br.readLine());
        goal.setLocation(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);

        // 미로의 구조를 입력받는다.
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // BFS로 탐색하며 탈출 위치에 도달했을 때 탐색 레벨(시작점에서 탈출 위치까지의 거리)를 출력한다.
        int level = 0;
        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                Progress check = queue.poll();

                // 탈출 위치에 도달했을 때 거리를 출력 후 종료한다.
                if(check.row == goal.x && check.col == goal.y) {
                    System.out.println(level);
                    return;
                }

                // 큐에서 poll 한 위치에서 상하좌우 방향의 위치를 검사한다.
                for (int j = 0; j < dirRow.length; j++) {
                    int newRow = check.row + dirRow[j], newCol = check.col + dirCol[j];
                    boolean isInside = newRow >= 0 && newRow < N && newCol >= 0 && newCol < M;
                    // 상하좌우 방향에 있는 위치가 미로 안에 있는 위치일 경우
                    if(isInside) {
                        // 이동하려는 위치가 벽이고, 사용 가능한 마법의 수가 남아있고, 이미 방문하지 않은 위치일 경우
                        if(map[newRow][newCol] == 1 && check.usedMagic < LIMIT_MAGIC && !visited[newRow][newCol][check.usedMagic + 1]) {
                            // 방문했다고 체크하고
                            visited[newRow][newCol][check.usedMagic + 1] = true;
                            // 사용한 마법의 수를 1 증가시켜 해당 위치와 함께 큐에 offer 한다.
                            queue.offer(new Progress(newRow, newCol, check.usedMagic + 1));
                        }

                        // 이동하려는 위치가 길이고, 이미 방문하지 않은 위치일 경우
                        else if (map[newRow][newCol] == 0 && !visited[newRow][newCol][check.usedMagic]) {
                            // 방문했다고 체크하고
                            visited[newRow][newCol][check.usedMagic] = true;
                            // 현재까지 사용한 마법의 수와 해당 위치를 큐에 offer 한다.
                            queue.offer(new Progress(newRow, newCol, check.usedMagic));
                        }
                    }
                }
            }
            level++; // 탐색 레벨 증가
        }

        System.out.println(-1); // 탈출할 수 없는 경우, -1 출력
    }
}