[BOJ] 5427. 불

BFS를 활용하는 문제이다.

이 문제의 경우 불(*)의 경우와 사람(@)의 경우가 있으므로 visit배열을 2차원 두개를 이용하기위해 3차원으로 선언하여 각 각 구분하여 문제를 접근하였다. 또한, 불길이 사람보다 먼저 번지기 때문에 일반적인 queue보단 deque를 이용하여 불길이 deque앞쪽에 들어가 있게 했다. 

위의 두가지 포인트가 기본적인 BFS 문제와 차이점을 보였던 문제이다.

package chap05;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main_bj_5427_불 {
 
    static int[] di = {-1,0,1,0};
    static int[] dj = {0,1,0,-1};
    
    static int[][][] visit;
    static char[][] map;
    
    static int N,M;
    static int result;
 
    static Deque<Pos> deque;
    
    static class Pos{
        int i,j,sec,person;
        public Pos(int i,int j,int s,int p) {
            this.i=i;this.j=j;sec=s;person=p;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =null;
        
        int T=Integer.parseInt(br.readLine());
        
        
        for(int tc=1;tc<=T;tc++) {
            st= new StringTokenizer(br.readLine());
            M=Integer.parseInt(st.nextToken());
            N=Integer.parseInt(st.nextToken());
            
            map=new char[N][M];
            visit = new int[N][M][2];
            for(int i=0;i<N;i++) {
                for(int j=0;j<M;j++) {
                    visit[i][j][0]=-1;
                    visit[i][j][1]=-1;
                }
            }
            deque=new LinkedList<>();
            
            for(int i=0;i<N;i++) {
                String str= br.readLine();
                for(int j=0;j<M;j++) {
                    char ch = str.charAt(j);
                    map[i][j]=ch;
                    if(ch=='*') {
                        deque.addFirst(new Pos(i, j, 0, 0));
                        visit[i][j][0]=0;
                    }else if(ch=='@') {
                        deque.addLast(new Pos(i, j, 0, 1));
                        visit[i][j][1]=0;
                    }
                    
                }
            }
            
            result=-1;
            
            bfs();
            
//            for(int i=0;i<N;i++) {
//                for(int j=0;j<M;j++) {
//                    System.out.print(visit[i][j][0]+"\t");
//                }
//                System.out.println();
//            }
//            System.out.println();
//            for(int i=0;i<N;i++) {
//                for(int j=0;j<M;j++) {
//                    System.out.print(visit[i][j][1]+"\t");
//                }
//                System.out.println();
//            }
            
            
            if(result==-1)
                System.out.println("IMPOSSIBLE");
            else
                System.out.println(result);
            
            
            
        }
    }
    static void bfs() {
        while(!deque.isEmpty()) {
            Pos cur = deque.poll();
            
            for(int dir=0;dir<4;dir++) {
                int nextI = cur.i+di[dir];
                int nextJ = cur.j+dj[dir];
 
                if(cur.person==0) {        //불꽃인경우
                    
                    if(nextI<0 || nextI>=N || nextJ<0 || nextJ>=M)
                        continue;
                    
                    // . 이고 불꽃이 간적이 없으면 불꽃 바로 갱신
                    if(map[nextI][nextJ]=='.' && visit[nextI][nextJ][0]==-1) {
                        visit[nextI][nextJ][0]=cur.sec+1;
                        deque.offer(new Pos(nextI, nextJ, cur.sec+1, 0));
                    }
                    
                    // @인데 
                    if(map[nextI][nextJ]=='@' && cur.sec+1 > visit[nextI][nextJ][1]) {
                        visit[nextI][nextJ][0]=cur.sec+1;
                        deque.offer(new Pos(nextI,nextJ,cur.sec+1,0));
                    }
                }else if(cur.person==1) {    //사람인 경우
                    
                    if(nextI<0 || nextI>=N || nextJ<0 || nextJ>=M) {
                        result=cur.sec+1;
                        return;
                    }
                    
                    //. 이고 내가 방문안한곳이면
                    if(map[nextI][nextJ]=='.' && visit[nextI][nextJ][1]==-1) {
                        if(visit[nextI][nextJ][0]==-1) {        //불길이 안간 곳
                            visit[nextI][nextJ][1]=cur.sec+1;
                            deque.offer(new Pos(nextI,nextJ,cur.sec+1,1));
                        }else if(visit[nextI][nextJ][0] > cur.sec+1) {        //불길이 간곳
                            visit[nextI][nextJ][1]=cur.sec+1;
                            deque.offer(new Pos(nextI,nextJ,cur.sec+1,1));
                        }
                        
                    }
                    
                }
                
            }
            
        }
        
        
    }
}