[백준 14442] 벽 부수고 이동하기 2

생각 정리

벽 부수고 이동하기 와 같은 로직으로 , 벽을 하나라도 부셨을 때의 비용과 하나도 부시지 않았을 때의 비용을 구한다.
다만, 다른 점은 부실 수 있는 벽이 1개가 아니고 K개 이기 때문에 그동안 부신 벽의 개수와 K개를 비교해간다.

생각하지 못한 것

벽을 부셨는지, 부시지 않았는지가 아니라 몇개를 부셨는지를 통해 나타내야 한다.
벽의 개수가 K개보다 많아지는 상황도 고려해야 한다.

코드

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

class Wall {
    int x, y; //현재 map의 위치
    int cnt; //지금까지 부순 벽의 개수

    Wall(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}

public class Main {
    static int N, K, M;
    static int[][] map;
    static int[][][] dist; //거리를 나타냄
    static boolean[][][] visited; 
    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());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        dist = new int[N][M][12];
        visited = new boolean[N][M][12];


        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(Character.toString(str.charAt(j)));
            }
        }

        bfs(0, 0);

    }

    static void bfs(int x, int y) {
        Queue<Wall> queue = new LinkedList<>();
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        boolean flag = false;

        if(map[x][y] == 0){ //벽이 아니면
            visited[x][y][0] = true;
            queue.add(new Wall(x, y, 0));

        } else {  //벽이면
            visited[x][y][1] = true;
            queue.add(new Wall(x, y, 1)); //

        }

        while(!queue.isEmpty()) {
            Wall out = queue.poll();

            if(out.x == N-1 && out.y == M-1 ){
                System.out.println(dist[out.x][out.y][out.cnt]+1);
                flag = true;
                return ;
            }

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

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


                int cnt = out.cnt;
                if(map[nx][ny] == 1)  cnt++;
                if(visited[nx][ny][cnt] || cnt > K) continue;


                visited[nx][ny][cnt] = true;
                queue.add(new Wall(nx, ny, cnt));
                dist[nx][ny][cnt] = dist[out.x][out.y][out.cnt] + 1;

               
            }
        }

        if(!flag)
            System.out.println(-1);
    }
    
}