[백준 14442] 벽 부수고 이동하기2 - 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)$에 대한 제한
  • $1 \leq K \leq 10$
  • 최대 10개의 벽을 부술 수 있다.

접근 방법

이전 벽 부수고 이동하기의 코드를 확장

• 이전에는 $z$가 0인 경우에만 벽을 부쉈는데
• 현재는 $K$의 범위가 늘어남에 따라 $z < K$인 경우에 벽 부수고 이동하는 $BFS$ 탐색을 수행
• 또한 visited 배열도 기존 2에서 $K+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());
        int K = 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, K, board));

    }

    private static int bfs(int N, int M, int K, char[][] board) {
        ArrayDeque<Node> q = new ArrayDeque<>();
        q.offer(new Node(0, 0, 0, 0));
        boolean[][][] visited = new boolean[K+1][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 < K) {
                        int nz = z + 1;
                        if (!visited[nz][ny][nx] && board[ny][nx] == '1') {
                            visited[nz][ny][nx] = true;
                            q.offer(new Node(nz, ny, nx, dist + 1));
                        }
                    }
                }
            }
        }
        return -1;
    }
}