[백준] 2206. 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

---

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

---

예제 입력 1

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1

15

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int m;
    static int[][] arr;
    static boolean[][][] visited;
    static int min;
    public static class Move {
        int p;
        int q;
        int count;
        boolean isBreak;
        public Move(int i, int j, int count, boolean isBreak){
            this.p = i;
            this.q = j;
            this.count = count;
            this.isBreak = isBreak;
        }
    }

    static int[] dp = {-1, 1, 0, 0};
    static int[] dq = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = sb.charAt(j) - '0';
            }
        }

        visited = new boolean[n][m][2];
        Queue<Move> queue = new LinkedList<>();

        queue.add(new Move(0, 0, 1, false));
        visited[0][0][0] = true;

        min = Integer.MAX_VALUE;
        while(!queue.isEmpty()) {
            Move move = queue.poll();
            if(move.p == n - 1 && move.q == m - 1) {
                if(move.count < min) {
                    min = move.count;
                }
                break;
            }
            
            for(int i = 0; i < 4; i++) {
                int np = move.p + dp[i];
                int nq = move.q + dq[i];

                if(np < 0 || nq < 0 || np >= n || nq >= m) {
                    continue;
                }
                if(visited[np][nq][move.isBreak ? 1 : 0]) {
                    continue;
                }
                if(arr[np][nq] == 0) {
                    visited[np][nq][move.isBreak ? 1 : 0] = true;
                    queue.add(new Move(np, nq, move.count + 1, move.isBreak));
                }
                if(arr[np][nq] == 1 && !move.isBreak) {
                    visited[np][nq][1] = true;
                    queue.add(new Move(np, nq, move.count + 1, true));
                }
            }
        }

        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }
}

큐를 이용한 bfs탐색이다.

현재의 위치를 Move라는 class로 만든다. Move 클래스에는 x좌표, y좌표, 벽을 부수었는지 안부쉈는지 boolean 값이 있다.

 

현재 위치를 큐에 넣고 해당 큐를 꺼내(Move move = queue.poll();) 4방향 위치를 큐에 다시 넣는다.

static int[] dp = {-1, 1, 0, 0};
static int[] dq = {0, 0, -1, 1};

위, 아래, 왼쪽, 오른쪽 방향으로 1칸씩 움직인 델타배열을 이용한다

int np = move.p + dp[i];
int nq = move.q + dq[i];

다음 좌표를 만들고 경계선을 넘지 않고 방문하지 않은 곳만 큐에 다시 넣는다.

 

일반 bfs와 다른점은 벽을 부수고 지나갔는지 그냥 지나갔는지를 확인하여 진행하여야 한다.

 

또한 visited배열을 3차원으로 만들었는데 벽을 부수었는지 안부수었는지를 기억하여야 하기 때문이다.

 

최종적으로 큐가 비었을때(진행을 모두 하였을 때) min값을 출력하면 된다.