#백준_2206 벽 부수고 이동하기 - Java 자바

# 유형 : 탐색, BFS

# 기존 bfs에서 조금 더 복잡해진 문제. 따로 저장할까 생각하려다가 벽을 뚫었는지 아닌지 체크하기위해 배열을 3차원으로 선언하여 문제를 해결.

 

벽 부술 곳을 하나하나 체크하면 당연히.. 시간초과가 날 것

 

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2206 {
    static int N,M;
    static int arr[][], map[][][];
    static int moveX[] = {0,-1,0,1};
    static int moveY[] = {-1,0,1,0};
    static ArrayList<Point> list = new ArrayList<>();
    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());
        arr = new int[N][M];
        map = new int[N][M][2];
        
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                int val = str.charAt(j)-'0';
                arr[i][j] = val;
            }
        }
        
        System.out.println(bfs(0,0));
    }
    
    public static int bfs(int i, int j) {
        Queue<Po> queue = new LinkedList<>();
        queue.add(new Po(i,j,1));
        map[i][j][1]=1;
        
        while(!queue.isEmpty()) {
            Po p = queue.poll();
            
            if(p.x == M-1 && p.y == N-1)
                return map[p.y][p.x][p.is];
            
            for(int d=0; d<4; d++) {
                int newY = p.y + moveY[d];
                int newX = p.x + moveX[d];
                
                if(0<=newY && newY<N && 0<=newX && newX<M) {
                    if(arr[newY][newX] == 1 && p.is==1) {
                        map[newY][newX][p.is-1] = map[p.y][p.x][p.is]+1;
                        queue.add(new Po(newX,newY,p.is-1));
                    }
                    else if(arr[newY][newX] == 0 && map[newY][newX][p.is] == 0) {
                        map[newY][newX][p.is] = map[p.y][p.x][p.is] + 1;
                        queue.add(new Po(newX,newY,p.is));
                    }
                }
            }
        }
        return -1;
    }
    
    public static class Po{
        int x;
        int y;
        int is;
        public Po(int x,int y,int is) {
            this.x=x;
            this.y=y;
            this.is=is;
        }
    }
}