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

boj-java-2206.java

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

public class Main {
    static int n,m;
    static int[][] map;
    static boolean[][][] visit;
    static Queue<Point> q;
    static int ans=1;
    static class Point{
        int r,c,b;//row column break step
        Point(int r, int c, int b){
            this.r = r;
            this.c = c;
            this.b = b;
        }
    }
    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));
        visit[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 k=0; k<4; k++){
                    int nr = curr.r + dr[k];
                    int nc = curr.c + dc[k];
                    if(nr<0 || n<=nr || nc<0 || m<=nc) continue;
                    if(map[nr][nc] == 0 && !visit[nr][nc][curr.b]){
                        visit[nr][nc][curr.b] = true;
                        q.offer(new Point(nr,nc,curr.b));
                    }else if(curr.b == 0 && !visit[nr][nc][1]){
                        visit[nr][nc][1] = true;
                        q.offer(new Point(nr,nc,1));
                    }
                }
            }
            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());
        map = new int[n][m];
        visit = new boolean[n][m][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();
    }
}