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

www.acmicpc.net/problem/16933

16933번: 벽 부수고 이동하기 3

벽을 몇개 부수는지 + 낮/밤 인지 까지 다양한 조건들이 들러붙은 BFS 문제다.

 

 

풀이의 앞서서 방문 체크를 한 배열에 대해 설명한다.

 

ch[x][y][0~1][0~k] 

 

3번째 차원의 의미는 0 이면 낮 / 1이면 밤이다.

4번째 차원의 의미는 0이면 0개의 벽을 부순 상태/ 1이면 1개의 벽을 부순 상태/ .../ k 이면 k개의 벽을 부순 상태 이다.

 

ch[1][2][1][1] = 10  이라면

 

(1,2) 위치에 현재 밤이며 벽을 1개 부섰을 때 최단 거리는 10이라는 의미다.

# 풀이

1. 현재 위치가 낮이라면?

    1-1. 현재 위치를 밤에 방문한적이 없다면 현재 위치의 밤에 방문한다.

    1-2. 다음 위치를 밤에 방문한 적이 없다면 다음 위치의 밤에 방문한다.

    1-3.* 다음 위치가 벽이면서 밤에 방문한 적이 없다면 다음 위치의 밤에 방문 한다.

 

2. 현재 위치가 밤이라면?

    2-1. 현재 위치를 낮에 방문한 적이 없다면 현재 위치의 낮에 방문한다.

    2-2. 다음 위치를 낮에 방문한 적이 없다면 다음 위치의 낮에 방문한다.

 

 

 

# 자바 코드

 

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

class Main{
    static int n,m,k;
    static int[][][][] ch;
    static int[][] arr;
    static int answer = Integer.MAX_VALUE;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        arr = new int[n][m];
        ch = new int[n][m][2][k+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';
            }
        }

        ch[0][0][0][0] = 1; // (0,0) night 0 wall
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0,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(p.day == 1){
                    // 현재 위치를 낮으로 변경
                    if(ch[p.x][p.y][0][p.k]==0){
                        ch[p.x][p.y][0][p.k] = ch[p.x][p.y][1][p.k]+1;
                        q.add(new Pair(p.x,p.y,0,p.k));
                    }

                    // 다음 위치를 낮으로 변경
                    if(arr[nx][ny] == 0 && ch[nx][ny][p.day-1][p.k]==0){
                        ch[nx][ny][0][p.k] = ch[p.x][p.y][1][p.k] + 1;
                        q.add(new Pair(nx,ny,0,p.k));
                    }
                }
                // 현재 낮인 경우
                else{
                    // 현재 위치를 밤으로 변경
                    if(ch[p.x][p.y][1][p.k]==0){
                        ch[p.x][p.y][1][p.k] = ch[p.x][p.y][0][p.k]+1;
                        q.add(new Pair(p.x,p.y,1,p.k));
                    }

                    // 밤으로 변경
                    if(arr[nx][ny] == 0 && ch[nx][ny][1][p.k]==0){
                        ch[nx][ny][1][p.k] = ch[p.x][p.y][0][p.k] + 1;
                        q.add(new Pair(nx,ny,1,p.k));
                    }

                    // 벽 부시기
                    if(arr[nx][ny] == 1 && p.k + 1 <= k && ch[nx][ny][1][p.k+1]==0){
                        ch[nx][ny][1][p.k+1] = ch[p.x][p.y][0][p.k] + 1;
                        q.add(new Pair(nx,ny,1,p.k+1));
                    }
                }
            }
        }

//        for(int r=0;r<k+1;r++) {
//            System.out.println(r+" 개 부시고 낮인 경우");
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < m; j++) {
//                    System.out.print(ch[i][j][0][r]);
//                }
//                System.out.println();
//            }
//            System.out.println();
//            System.out.println(r+" 개 부시고 인 경우");
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < m; j++) {
//                    System.out.print(ch[i][j][1][r]);
//                }
//                System.out.println();
//            }
//            System.out.println();
//        }

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


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


    }


    static class Pair{
        int x,y,day,k;

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