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

문제

 

풀이

이 문제는 예전에 BFS를 한창 풀었을 때에는 못 풀었던 문제였는데 이와 유사한 문제인 1600. 말이 되고픈 원숭이문제를 풀고 영감을 얻어서 다시 도전했더니 쉽게 풀렸다. 

이 문제가 일반적인 BFS보다 까다로운 이유는 어떤 좌표에 올 수 있는 경우의 수가 2가지(이전에 벽을 부신 경우, 이전에 벽을 부수지 않은 경우)라는 점이다. 따라서 2차원 방문 배열로는 처리가 불가능하고 3차원 배열을 사용하여 문제를 해결하였다. 3차원 배열에서 0번쨰 인덱스는 벽을 이미 부수고 온 경우, 1번째 인덱스는 벽을 아직 부수지 않은 경우이다.

bfs를 진행하며 다음의 3가지 경우에 대해서 처리해주었다.

1. 현재 벽을 부술 수 있는 기회가 남아있고 다음 방문할 좌표가 벽인 경우, 기회를 소진하고 벽을 방문
2. 기회가 남아있지만 다음 방문할 좌표가 벽이 아닌 경우에는 기회를 사용하지 않고 다음 지점으로 방문
3. 기회가 남아있지 않다면 다음 방문할 좌표가 벽이 아닌 경우만 방문

구현한 코드는 다음과 같다.

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

public class Solution2206 {
    static class Pair {
        int x;
        int y;
        int dist;
        int remain;

        public Pair(int x, int y, int dist, int remain) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.remain = remain;
        }
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, M;
    static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
    static int[][] map;
    static boolean[][][] visited;
    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        map = new int[N][M];
        visited = new boolean[N][M][2];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = Character.getNumericValue(line.charAt(j));
            }
        }

        System.out.println(bfs());
    }

    private static int bfs() {
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0, 0, 1, 1));
        while (!q.isEmpty()) {
            Pair cur = q.poll();
            if (cur.x == N - 1 && cur.y == M - 1) return cur.dist;
            if (cur.remain == 1) {
                for (int i = 0; i < 4; i++) {
                    int nX = cur.x + dx[i];
                    int nY = cur.y + dy[i];
                    if (nX < 0 || nY < 0 || nX >= N || nY >= M) continue;
                    if (map[nX][nY] == 1 && !visited[nX][nY][0]) {
                        visited[nX][nY][0] = true;
                        q.add(new Pair(nX, nY, cur.dist + 1, 0));
                    } else if (map[nX][nY] == 0 && !visited[nX][nY][1]) {
                        visited[nX][nY][1] = true;
                        q.add(new Pair(nX, nY, cur.dist + 1, 1));
                    }
                }
            }

            for (int i = 0; i < 4; i++) {
                int nX = cur.x + dx[i];
                int nY = cur.y + dy[i];
                if (nX < 0 || nY < 0 || nX >= N || nY >= M || visited[nX][nY][cur.remain] || map[nX][nY] == 1) continue;
                visited[nX][nY][cur.remain] = true;
                q.add(new Pair(nX, nY, cur.dist + 1, cur.remain));
            }
        }

        return -1;
    }
}