4179번 : 불! [JAVA]

문제 링크

성공 여부(걸린 시간): 성공 (44분 39초)

아이디어

우선 BFS를 돌아주는데 다음 갈 수 있는 지점들을 매번 갱신해주며 가려고 했다.
BFS는 시간마다 총 2번 시행된다.(불의 확산과 지훈이의 이동)

 

불의 확산

불은 현재의 불들을 큐에 넣고 다음 불탈 수 있는 위치를 따로 ArrayList에 저장해준다.
그다음 불의 확산 BFS가 끝나면 ArrayList에 저장된 불의 확산가능한 위치들을 큐에 다시 넣는다.
이렇게 하면 턴(시간)마다 구분된 동작이 가능하다.

 

지훈이의 이동

거의 동일한 방식으로 지훈이의 이동도 구현했다. 그러나 조금 다른점은
지훈이가 다음 이동할 좌표를 추가할때 만약 좌표밖으로 나간다면
이것은 무사히 탈출한 것이므로 시간을 출력하고 return해준다.

그리고 다음 이동할 지훈이의 위치가 저장된 ArrayList인 jNext가 비어있다면
더이상 이동치 못하기에 IMPOSSIBLE을 출력하고 종료한다.

⚠️⚠️⚠️주의할 점⚠️⚠️⚠️

처음 입력받을때 지훈이와 불의 시작점을 입력받고 시작했는데
당연히 불이 하나일 것이라고 생각해서 11%에서 자꾸 막혔다.

그래서 불을 여러개라고 고쳤더니 54%쯤에서 막혔다.

그이유는 각 BFS를 통해 지훈이가 이동하고 불을 확산 시켰는데
동시에 불과 지훈이가 확산과 이동을 하는 것이기 때문에

불을 먼저 확산시켜야 알맞은 답이 나왔다.

정답 코드

import java.util.*;
import java.io.*;

class Main{
    static int N, M;
    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());
        char [][] map = new char [N][M];
        ArrayDeque<int []> jQ = new ArrayDeque<>();
        ArrayDeque<int []> fQ = new ArrayDeque<>();
        boolean [][] visited = new boolean[N][M];
        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<M; j++){
                char x= str.charAt(j);
                map[i][j] = x;
                if(x =='J'){
                    jQ.add(new int[]{i, j});
                    visited[i][j] = true;
                }
                else if(x =='F'){
                    fQ.add(new int[]{i, j});
                }
            }
        }
        int [] dx = {1, 0, -1, 0};
        int [] dy = {0, 1, 0, -1};
        for(int run =1; ; run++){
            //불이 없는 경우는 그냥 넘어감
            //새로운 불 위치 넣기 -> 번질 수 있는 불
            ArrayList<int []> fNext = new ArrayList<>();
            while(!fQ.isEmpty()){
                int [] cur = fQ.poll();
                for(int i=0; i<4; i++){
                    int mx = cur[0]+dx[i];
                    int my = cur[1]+dy[i];
                    if(canGo(mx, my)&&map[mx][my]=='.'){
                        fNext.add(new int[]{mx, my});
                        map[mx][my] = 'F';
                    }
                }
            }
            if(!fNext.isEmpty()){
                fQ.addAll(fNext);
            }
            //지훈 이동가능 좌표 넣기
            ArrayList<int []> jNext = new ArrayList<>();
            while(!jQ.isEmpty()){
                int [] cur = jQ.poll();
                for(int i=0; i<4; i++){
                    int mx = cur[0]+dx[i];
                    int my = cur[1]+dy[i];
                    if(!canGo(mx, my)){
                        System.out.print(run);
                        return;
                    }
                    if(canGo(mx,my) && map[mx][my]=='.'&&!visited[mx][my]){
                        jNext.add(new int[]{mx, my});
                        visited[mx][my] = true;
                    }
                }
            }
            if(jNext.isEmpty()){
                System.out.print("IMPOSSIBLE");
                return;
            }
            else{
                jQ.addAll(jNext);
            }

        }
    }
    static boolean canGo(int x, int y){
        return x>=0&&y>=0&&x<N&&y<M;
    }
}
// 지훈이가 움직일 수 있는 위치 BFS로 리스트 저장 (.으로 이동)
// 불이 확산되는 BFS 1회 수행(새로 추가된 불들은 다음 BFS에서 돌아줘야함)
// 다음 움직일 지점이 탈출지점이라면 종료

솔직히 문제조건이 너무 빈약했다.