[JAVA] 백준(14442) - 벽 부수고 이동하기 2 (BFS)

www.acmicpc.net/problem/14442

14442번: 벽 부수고 이동하기 2

 

벽을 최대 K 개 부술수 있다.

 

벽을 부수지 않은 경우  / 1개 부순 경우 / 2개 부순 경우 .... / K개 부순경우 경우를 나눠서 방문 체크를 하며 BFS 하면된다.

 

평범한 2차원 배열의 BFS라면 2차원 배열로 해당 위치를 방문 체크하면 되지만 경우를 나눠서 방문 체크하는 이유는 다음과 같다.

 

만약 ( x, y )  라는 위치에 먼저 방문했다고 해서 최단거리임을 보증할 수 없기 때문이다.

 

 

START 에서 END 까지 최단 거리는 5이다. ( 시작 ~ 끝 포함)

 

하지만 END 는 벽을 1개 부수고 도착한 것인지 아니면 그냥 온것인지 2개 부수고 온것인지 보증할 길이 없다.

 

따라서 1개 부수고 온지 2개 부수고 온지 등 체크할 방문 배열을 따로 만들어 줘야하는 것이다.

 

전체 코드는 아래와 같다.

 

import java.util.*;
import java.util.LinkedList;

class Main{
    static int arr[][] = new int[1000][1000];
    static int n,m,k;

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

    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();

        dist = new int[n][m][k+1];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                for(int m=0;m<k+1;m++){
                    dist[i][j][m] = -1;
                }
            }
        }

        for(int i=0;i<n;i++){
            char[] temp  = sc.next().toCharArray();
            for(int j=0;j<m;j++){
                arr[i][j] = temp[j] - '0';
            }
        }

        Queue<Pair> q = new LinkedList<>();
        dist[0][0][0] = 1;
        q.add(new Pair(0,0,0));
        while(!q.isEmpty()){
            Pair p = q.poll();

            for(int i=0;i<4;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(nx <0 || nx>=n || ny <0 || ny>=m ) continue;
                if(arr[nx][ny]==0 && dist[nx][ny][p.k]==-1){
                    dist[nx][ny][p.k] = dist[p.x][p.y][p.k] + 1;
                    q.add(new Pair(nx,ny,p.k));
                }
                if(arr[nx][ny] == 1 && p.k+1<=k && dist[nx][ny][p.k+1]==-1){
                    dist[nx][ny][p.k+1] = dist[p.x][p.y][p.k]+1;
                    q.add(new Pair(nx,ny,p.k+1));
                }
            }
        }

        for(int i=0;i<=k;i++){
            if(dist[n-1][m-1][i] != -1){
                answer = Math.min(answer,dist[n-1][m-1][i]);
            }
        }

        System.out.println(answer!=Integer.MAX_VALUE?answer:-1);

    }

    static class Pair{
        int x,y,k;

        public Pair(int x,int y,int k){
            this.x = x;
            this.y = y;
            this.k = k;
        }
    }


}