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

과거에 풀었던 문제입니다. 노션에 기록된 내용을 바탕으로 정리했습니다.

문제 파악

문제

• $N*M$으로 표현되는 맵이 존재하고 맵 안에는 벽이 존재할 때
• $(1, 1)$ 부터 $(N, M)$ 까지 이동하려 할 때 최단 경로 구하기

제한 사항

• $1≤N,\;M≤1,000$
• 각 칸은 0 또는 1로 이루어진 2차원 배열
  • $map[i][j]\;∈\;\{0,1\}\;for\; 1≤i≤N,\; 1≤j≤M$
• 벽$(K)$에 대한 제한
  • 0: 이동 가능
  • 1: 벽 (최대 한 번만 부술 수 있음)

반환

• 최단 거리 출력
• 불가능 시 -1 출력

접근 방법

Programmers의 보물찾기와 동일한 유형

• 기존 BFS 알고리즘에 벽을 부수고 탐색하는 경우를 추가
  • 나머지 로직은 기존 BFS와 동일
• visited를 3차원으로 선언해서 하나의 차원을 벽을 부순 횟수를 기록
  • 즉 visited[1][2][3] 의 의미는 (2, 3)에 벽을 1번 부수고 방문했다는 의미
• 기존 상/하/좌/우에 대한 탐색 + 벽을 부순 적이 없고(visited[0][?][?]) 해당 좌표가 벽인 경우 ⇒ 벽을 부수고 탐색(visited[1][?][?])

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

class Node {
    int z;
    int y;
    int x;
    int dist;
    public Node (int z, int y, int x, int dist) {
        this.z = z;
        this.y = y;
        this.x = x;
        this.dist = dist;
    }
}

public class Main {
    static StringTokenizer st;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        char[][] board = new char[N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                board[i][j] = s.charAt(j);
            }
        }

        System.out.println(bfs(N, M, board));

    }

    private static int bfs(int N, int M, char[][] board) {
        ArrayDeque<Node> q = new ArrayDeque<>();
        q.offer(new Node(0, 0, 0, 0));
        boolean[][][] visited = new boolean[2][N][M];
        visited[0][0][0] = true;

        int ey = N-1;
        int ex = M-1;

        while (!q.isEmpty()) {
            Node node = q.poll();
            int z = node.z;
            int y = node.y;
            int x = node.x;
            int dist = node.dist;

            if (y == ey && x == ex) return dist + 1;

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

                if (0 <= ny && ny < N && 0 <= nx && nx < M) {
                    if (!visited[z][ny][nx] && board[ny][nx] == '0') {
                        visited[z][ny][nx] = true;
                        q.offer(new Node(z, ny, nx, dist + 1));
                    }
                    if (z == 0) {
                        if (!visited[1][ny][nx] && board[ny][nx] == '1') {
                            visited[1][ny][nx] = true;
                            q.offer(new Node(1, ny, nx, dist + 1));
                        }
                    }
                }
            }
        }
        return -1;
    }
}