[Algorithm/Java] 백준 14442번 - 벽 부수고 이동하기 2

---

https://www.acmicpc.net/problem/14442

---

🔍 문제 풀이

풀이 방법

💻 코드

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr;
    static int[][][] v;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int n, m, k;

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

        // input
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        v = new int[n][m][k + 1]; // [x][y][벽 부순 개수]

        for(int i=0; i<n; i++) {
            String line = br.readLine();
            for(int j=0; j<m; j++){
                arr[i][j] = line.charAt(j) - '0';
            }
        }

        // solve
        int ans = bfs(0, 0);

        // output
        System.out.println(ans);
    }

    static int bfs(int x, int y){
        // 1. 초기화
        Deque<Pos> dq = new ArrayDeque<>();

        // 2. 초기값
        dq.offer(new Pos(x, y, 0));
        v[x][y][0] = 1; // 시작점 포함

        // 3. 탐색
        while(!dq.isEmpty()) {
            Pos cur = dq.poll();

            // 3.1 종료조건
            if (cur.x == n-1 && cur.y == m-1) {
                return v[cur.x][cur.y][cur.broken];
            }

            // 3.2 4방향, 범위
            for(int d = 0; d<4; d++) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

                // 1. 다음 칸이 통로(0)인 경우
                if (arr[nx][ny] == 0) {
                    // 현재 부순 개수로 상태로 다음 칸에 방문한 적이 없다면
                    if (v[nx][ny][cur.broken] == 0) {
                        v[nx][ny][cur.broken] = v[cur.x][cur.y][cur.broken] + 1;
                        dq.offer(new Pos(nx, ny, cur.broken)); // 상태 유지
                    }
                }

                // 2. 다음 칸이 벽(1)인 경우 -> 벽을 부술지 결정
                else {
                    // 벽 부술 기회 있다면
                    if (cur.broken < k) {
                        int nextBroken = cur.broken + 1;

                        // 벽을 부순 새로운 상태로 다음 칸에 방문한 적이 없다면
                        if (v[nx][ny][nextBroken] == 0) {
                            v[nx][ny][nextBroken] = v[cur.x][cur.y][cur.broken] + 1;
                            dq.offer(new Pos(nx, ny, nextBroken)); // 상태 + 1
                        }
                    }

                }
            }
        }
        return -1;
    }

    static class Pos{
        int x, y, broken;
        Pos(int x, int y, int broken) {
            this.x = x;
            this.y = y;
            this.broken = broken;
        }
    }
}