[PS][java][완전탐색][BFS]/[벽 부수고 이동하기3]

boj-java-16933.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n,m,k;
    static int[][] map;
    static boolean[][][][] visit;
    static Queue<Point> q;
    static int ans=1;
    static class Point{
        int r,c,b;
        boolean d;//row column break day
        Point(int r, int c, int b, boolean d){
            this.r = r;
            this.c = c;
            this.b = b;
            this.d = d;
        }
    }
    static int[] dr = {0,0,1,-1};
    static int[] dc = {1,-1,0,0};

    static void showMap(){
        for(int i=0; i< n; i++){
            for(int j=0; j<m; j++){
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    static void bfs(){
        q = new LinkedList<>();
        q.offer(new Point(0,0,0, true));
        visit[0][0][0][0] = true;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                Point curr = q.poll();
                if(curr.r == n-1 && curr.c == m-1){
                    System.out.println(ans);
                    return;
                }
                for(int j=0; j<4; j++){
                    int nr = curr.r + dr[j];
                    int nc = curr.c + dc[j];
                    int nd = !curr.d == true ? 0 : 1;
                    if(nr<0 || n<=nr || nc<0 || m<=nc) continue;
                    if(map[nr][nc] == 0 && !visit[nr][nc][curr.b][nd]){
                        visit[nr][nc][curr.b][nd] = true;
                        q.offer(new Point(nr,nc,curr.b,!curr.d));
                    }else if(nd == 0 && curr.b<k && !visit[curr.r][curr.c][curr.b][nd]){
                        q.offer(new Point(curr.r,curr.c,curr.b,!curr.d));
                    }else if(nd == 1 && curr.b<k && !visit[nr][nc][curr.b+1][nd]){
                        visit[nr][nc][curr.b+1][nd] = true;
                        q.offer(new Point(nr,nc,curr.b+1,!curr.d));
                    }
                }
            }
            ans++;
        }
        System.out.println(-1);
    }

    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];
        visit = new boolean[n][m][k+1][2];
        for(int i=0; i< n; i++){
            String line = br.readLine();
            for(int j=0; j<m; j++){
                map[i][j] = line.charAt(j)-'0';
            }
        }
//        showMap();
        bfs();
    }
}