[백준] 2206. 벽 부수고 이동하기 (그래프 탐색 / Java)

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

 

📌 풀이 과정

벽이 존재하는 미로에서 (0,0)에서 시작해 (N-1,M-1)까지 이동해야 하며, 이동 중에 벽을 한 번 부수는 것이 허용되는 문제다.

BFS 탐색 중, 같은 좌표 (x, y)에 도착했더라도 벽을 부수고 도착했는지
부수지 않고 도착했는지를 구분해야 하기 때문에 3차원 방문 배열을 사용해야 한다.

 

3차원 방문 배열의 사용

• visited[x][y][0]: 좌표 (x, y)에 벽을 부수지 않고 방문한 상태
• visited[x][y][1]: 좌표 (x, y)에 벽을 한 번 부수고 방문한 상태

 

이동 가능한 좌표 탐색

1. 벽이 아닌 곳으로 이동
   • 다음으로 이동하려는 좌표가 map[nx][ny] = 0 이고, 현재 상태(broke)에 맞는 방문처리가 false라면 해당 좌표로 이동한다.
2. 벽이 있는 곳으로 이동
   • 벽이 있는 좌표 map[nx][ny] = 1 이면서, 벽을 아직 부순적이 없다면 broke = 0 벽을 부수고 이동한다.
   • 이 경우 visited[nx][ny][1] = true 로 설정하고, 큐에 벽을 부순 상태로 해당 좌표를 추가한다.

 

✨ 제출 코드

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

/**
 * 메모리: 149236 KB
 * 시간: 760 ms
 */
public class Main {

    static int N, M;
    static int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int[][] map;

    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];

        for (int i = 0; i < N; i++) {
            char[] input = br.readLine().toCharArray();
            for(int j = 0; j < M; j++) {
                map[i][j] = input[j] - '0';
            }
        }

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

    private static int bfs(){
        Queue<int[]> q = new LinkedList<>();
        boolean[][][] visited = new boolean[N][M][2];
        q.add(new int[]{0, 0, 1, 0}); // (0, 0) 좌표에서 시작
        visited[0][0][0] = true; // 벽을 부수지 않고 시작점을 방문 처리

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0];
            int y = cur[1];
            int depth = cur[2];
            int broke = cur[3];

            if(x == N-1 && y == M-1) return depth;

            for(int i = 0; i < 4; i++){
                int nx = x + d[i][0];
                int ny = y + d[i][1];

                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

                // 이동할 수 있는 곳인 경우 (벽이 아님)
                if(map[nx][ny] == 0 && !visited[nx][ny][broke]){
                    visited[nx][ny][broke] = true;
                    q.add(new int[]{nx, ny, depth + 1, broke});
                }

                // 벽이 있는 경우, 벽을 부수지 않은 상태에서만 벽을 부순다
                if(broke == 0 && map[nx][ny] == 1 && !visited[nx][ny][1]){
                    visited[nx][ny][1] = true; // 벽을 부수고 방문 처리
                    q.add(new int[]{nx, ny, depth + 1, 1});
                }

            }
        }
        return -1;
    }
}