[BOJ] 2206. 벽 부수고 이동하기

 

최단거리를 구하는 문제이기에 BFS를 사용하는 문제이다.

이 문제에선 신경써야할 점이 두가지 있다. 첫째, visit[][][]을 이용하여 벽을 뚫지 않은 상태에서랑 벽을 이미 한번 뚫은 상태에서 방문이 가능한지 신경써줘야한다. 둘째, queue에서 poll 할때 목적지 지점이면 최솟값으로 갱신 가능한지 확인하는 것 이다.

package chap05;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_2206_벽부수고이동하기 {
    
    
    static int N,M;
    
    static int[] di = {-1,0,1,0};
    static int[] dj = {0,1,0,-1};
    
    static int[][] map;
    static boolean[][][] visit;
    static int result;
 
    static Queue<Pos> queue;
    
    static class Pos{
        int i,j,dis;
        int brokenWall;
        
        public Pos(int i,int j,int d, int b) {
            this.i=i;this.j=j;this.dis=d;this.brokenWall=b;
        }
    }
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        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 str = br.readLine();
            for(int j=0;j<M;j++) {
                map[i][j]=str.charAt(j) -'0';
            }
        }
        
        queue =new LinkedList<>();
        
        result=Integer.MAX_VALUE;
        bfs();
        if(result==Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(result);
    }
    
    
    static void bfs() {
        queue.offer(new Pos(0, 0, 1, 0));
        visit[0][0][0]=true;
        
        while(!queue.isEmpty()) {
            Pos cur = queue.poll();
            
            if(cur.i ==N-1 && cur.j==M-1) {            //최단거리비교
                result = Math.min(result, cur.dis);
                continue;
            }
            
            for(int dir=0;dir<4;dir++) {
                int nextI=cur.i+ di[dir];
                int nextJ=cur.j+ dj[dir];
                
                if(nextI<0||nextI>=N || nextJ<0 ||nextJ>=M)
                    continue;
                
                if(cur.brokenWall==0) {    //벽을 부순적 없는상태
                    if(map[nextI][nextJ]==0 && visit[nextI][nextJ][0]==false) {    //갈수있는곳
                        visit[nextI][nextJ][0]=true;
                        queue.offer(new Pos(nextI, nextJ, cur.dis+1, 0));
                    }else if(map[nextI][nextJ]==1 && visit[nextI][nextJ][1]==false) {    //벽인곳
                        visit[nextI][nextJ][1]=true;
                        queue.offer(new Pos(nextI, nextJ, cur.dis+1, 1));
                    }
                }else if(cur.brokenWall==1) {    //벽을 부순 상태
                    if(map[nextI][nextJ]==0 && visit[nextI][nextJ][1]==false) {        // 갈수있는곳
                        visit[nextI][nextJ][1]=true;
                        queue.offer(new Pos(nextI, nextJ, cur.dis+1, 1));
                    }
                }
            }
        }
        
    }
 
 
}