[필수 문제] 목수의 미로 탈출

1. 문제

아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 찾으려 한다. 그런데 목수는 도끼 하나를 갖고 있으며, 이 도끼를 이용하여 벽을 깨부술 수 있다. 하지만 이 도끼는 내구성이 그렇게 좋지 않기 때문에, 벽을 최대 1개밖에 깰 수 없다. 목수가 출발점에서 도착점까지 이동하기 위한 최단거리를 출력하는 프로그램을 작성하시오. 물론, 벽은 최대 1개까지 깰 수 있다. 아래 예제의 경우 ‘X’ 로 표시된 벽을 깰 경우 거리 18만에 출발점에서 도착점으로 이동할 수 있다.

---

입력

첫째 줄에 지도의 세로 길이 N과 지도의 가로 길이 M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 둘째 줄부터 지도의 정보가 주어진다. 0은 이동할 수 있는 부분, 1은 이동할 수 없는 부분을 나타낸다.

출력

목수가 (N-1, 0) 에서 출발하여 (0, M-1) 까지 이동하는 데 필요한 최단거리를 출력한다. 목수는 미로를 항상 탈출할 수 있다고 가정한다.

예제 입력

10 10
0 0 0 0 0 0 1 1 0 0
0 1 1 1 0 0 1 0 1 0 
0 1 1 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 1 0
0 0 1 1 1 1 0 0 1 0
0 0 0 0 0 0 1 1 0 0
0 0 1 1 1 0 1 1 0 0
0 0 1 1 1 0 0 0 0 0 
0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 0 0

예제 출력

18

 

 

 

2. 풀이

이 문제는 2개의 방문 상태로 나누면 풀 수 있다.

• 벽을 부수기 전 방문 상태
• 벽을 부순 후 방문 상태

import java.io.*;
import java.util.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int m;

    private static int[][] arr;
    private static int[][] dist;
    private static boolean[][] isNotBroken;
    private static boolean[][] isBroken;

    private static int[] dy = {-1, 1, 0, 0};
    private static int[] dx = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        dist = new int[n][m];
        isNotBroken = new boolean[n][m];
        isBroken = new boolean[n][m];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bfs(n-1, 0);

        bw.write(dist[0][m-1] + "");
        br.close();
        bw.flush();
        bw.close();
    }

    private static void bfs(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {i, j, 0}); // 0은 한번도 부수지 않은 상태, 1은 한번 부순 상태
        isNotBroken[i][j] = true;

        while(!queue.isEmpty()) {
            if(dist[0][m-1] != 0 ) break;
            int[] w = queue.poll();

            for(int k = 0; k < 4; k++) {
                int y = w[0] + dy[k];
                int x = w[1] + dx[k];
                int b = w[2];

                if(y >= 0 && y < n && x >=0 && x < m) {
                    if(b == 1) { // 벽을 이미 한번 부순 상태
                        if(!isNotBroken[y][x] && !isBroken[y][x] && arr[y][x] == 0) {
                            queue.add(new int[]{y, x, 1});
                            dist[y][x] = dist[w[0]][w[1]] + 1;
                            isBroken[y][x] = true;
                        }
                    } else { // 한번도 벽을 부수지 않은 상태
                        if(!isNotBroken[y][x]) {
                            if(arr[y][x] == 0) queue.add(new int[] {y, x, 0});
                            else if(arr[y][x] == 1) queue.add(new int[] {y, x, 1});
                            dist[y][x] = dist[w[0]][w[1]] + 1;
                            isNotBroken[y][x] = true;
                        }
                    }
                }
            }
        }
    }
}