[BOJ2206] 벽 부수고 이동하기

[문제링크]

풀이

1. 접근 방법

최단 경로 문제이므로 BFS를 사용하는 것이 표준적인 접근. 하지만 '벽을 한 번까지 부술 수 있다'는 조건 때문에 방문 상태를 단순 2차원 배열로 관리할 수 없다. 벽을 부순 상태와 부수지 않은 상태를 구별하여 경로를 탐색해야 하므로, 3차원 배열 visited[row][col][wall_broken_status]를 도입하여 상태를 관리한다.

2. 사고 흐름

1. (N, M)까지의 최단 거리를 구하는 문제이므로 BFS를 떠올린다.
2. 기본적인 BFS는 큐에 좌표 (x, y)를 저장하고 visited[x][y]로 방문 여부를 체크한다.
3. 하지만 이 문제에서는 벽을 한 번 부수는 것이 허용된다. 예를 들어, (r, c)에 벽을 부수고 도달하는 경로와, 벽을 부수지 않고 도달하는 경로는 이후의 탐색에 다른 영향을 미친다. (전자는 더 이상 벽을 부술 수 없고, 후자는 아직 기회가 있다.)
4. 따라서, 같은 좌표라도 '벽 파괴 여부'에 따라 다른 상태로 취급해야 한다. (x, y, broken)을 하나의 상태 단위로 정의한다.
5. 이에 따라 방문 배열도 visited[x][y][broken]의 3차원으로 확장한다. visited[x][y][0]은 (x,y)까지 벽을 한 번도 부수지 않고 도착했음을 의미하고, visited[x][y][1]은 벽을 한 번 부수고 도착했음을 의미한다.
6. 이 상태 정의를 기반으로 BFS를 설계한다.

3. 동작 방식

BFS 큐에 (x, y, 거리, 벽 파괴 여부)를 저장하여 탐색을 진행한다.

1. 초기 상태 (0, 0, 1, 0) (위치, 거리, 파괴안함)를 큐에 추가하고 visited[0][0][0]을 방문 처리한다.
2. 큐가 빌 때까지 다음을 반복한다:
   • 큐에서 현재 상태 (x, y, dist, broken)를 꺼낸다.
   • 도착점 (N-1, M-1)에 도달하면 dist를 반환하고 종료한다.
   • 상하좌우 인접 칸 (nx, ny)를 탐색한다.
     • 벽이 아닌 경우 (map[nx][ny] == 0): visited[nx][ny][broken]이 아직 방문하지 않은 상태라면, (nx, ny, dist + 1, broken)을 큐에 추가하고 방문 처리한다.
     • 벽인 경우 (map[nx][ny] == 1): 아직 벽을 부순 적이 없고(broken == 0), visited[nx][ny][1]이 아직 방문하지 않은 상태라면, 벽을 부수고 이동하는 새로운 상태 (nx, ny, dist + 1, 1)을 큐에 추가하고 방문 처리한다.
3. 큐가 모두 비워질 때까지 도착점에 도달하지 못하면, 경로가 없는 것이므로 -1을 반환한다.

4. 코드

//BOJ2206 벽 부수고 이동하기
//[www.acmicpc.net/problem/2206](http://www.acmicpc.net/problem/2206)

package BOJ2206;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Stream;

public class Main {
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};
    static int[][] map;
    static boolean[][][] visited;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader([System.in](http://System.in)));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M][2];
        for (int i = 0; i < N; i++) {
            map[i] = Stream.of(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        }
        System.out.println(bfs());
    }

    public static int bfs() {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, 0, 1, 0});//x, y, depth, walls
        visited[0][0][0] = true; //정상 이동
        visited[0][0][1] = true; //벽 부수고 이동
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];
            int dist = cur[2];
            int broken = cur[3];
            if (x == N - 1 && y == M - 1) {
                return dist;
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (isValid(nx, ny)) {
                    // 다음 이동할 곳이 벽이 아닌 경우
                    if (map[nx][ny] == 0) {
                        // 해당 상태(broken)로 아직 방문하지 않았다면
                        if (!visited[nx][ny][broken]) {
                            visited[nx][ny][broken] = true;
                            queue.offer(new int[]{nx, ny, dist + 1, broken});
                        }
                    }
                    // 다음 이동할 곳이 벽인 경우
                    else {
                        // 벽을 부술 기회가 남아있고, 벽을 부순 상태로 아직 방문하지 않았다면
                        if (broken == 0 && !visited[nx][ny][1]) {
                            visited[nx][ny][1] = true;
                            // 벽을 부쉈으므로 상태를 1로 변경
                            queue.offer(new int[]{nx, ny, dist + 1, 1});
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static boolean isValid(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }
}