[백준] 5427번 : 불 - JAVA [자바]

https://www.acmicpc.net/problem/5427

---

📝 문제 설명

사람은 #(벽)을 이동할 수 없으며 *(불)을 피해서.(빈 공간)만을 이동할 수 있다. 사람은 불이 있는 칸과 이제 불이 번지려는 칸을 피해서 경계선에 도착해 탈출해야 한다. 사람은 불이 먼저 이동하고 그 후에 이동해야 한다. 이는 1초가 걸린다. 탈출하는데 가장 빠른 시간을 출력하고 탈출을 하지 못하면 IMPOSSIBLE을 출력하면 된다.

✨ 제출 코드

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

public class Main{
    static int [] dx = {-1,1,0,0};
    static int [] dy = {0,0,-1,1};

    static int w,h;
    static char [][] graph;
    static boolean [][]visited;

    static Queue<int []> fireQ;
    static Queue<int []> personQ;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < T; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            graph = new char [h][w];
            visited = new boolean [h][w];

            fireQ = new LinkedList<>();
            personQ = new LinkedList<>();

            for(int j = 0; j < h; j++){
                String str = br.readLine();
                for(int k = 0; k < w; k++){
                    graph[j][k] = str.charAt(k);

                    //입력받으면서 personQ에 넣기
                    if(graph[j][k] == '@'){
                        personQ.offer(new int [] {j,k});
                        visited[j][k] = true;
                    }

                    //입력받으면서 fireQ에 넣기
                    if(graph[j][k] == '*'){
                        fireQ.offer(new int [] {j,k});
                    }
                }
            }

            int result = bfs();

            if(result == -1) sb.append("IMPOSSIBLE\n");
            else sb.append(result+"\n");
        }

        System.out.println(sb);
    }
    static int bfs(){
        int time = 0;

        //한 턴 1초
        while(!personQ.isEmpty()){
            time ++;

            //불 먼저 이동
            int fireQsize = fireQ.size(); 

            //해당 턴의 fireQ가 번지는 칸만 확인 while(!fireQ.isEmpty()) 안됨
            for(int i = 0; i < fireQsize; i++){
                int [] cur = fireQ.poll();

                for(int d = 0; d < 4; d++){
                    int nx = cur[0] + dx[d];
                    int ny = cur[1] + dy[d];
    
                    if(nx>=0 && nx<h && ny>=0 && ny<w){
                        if(graph[nx][ny] == '.'){
                            graph[nx][ny] = '*';
                            fireQ.offer(new int [] {nx,ny});
                        }
                    }
                }
            }

            //사람 이동
            int personQsize = personQ.size();
            for(int i = 0; i < personQsize; i++){
                int [] cur = personQ.poll();

                // 벽에 닿으면 탈출 성공
                if (cur[0] == 0 || cur[0] == h - 1 || cur[1] == 0 || cur[1] == w - 1) {
                    return time;
                }

                for(int d = 0; d < 4; d++){
                    int nx = cur[0] + dx[d];
                    int ny = cur[1] + dy[d];
    
                    if(nx>=0 && nx<h && ny>=0 && ny<w){
                        if(graph[nx][ny] == '.' && !visited[nx][ny]){
                            visited[nx][ny] = true;
                            personQ.offer(new int [] {nx,ny});
                        }
                    }
                }
            }   
        }
        return -1;
    }
}

 

✌️ 코드 설명

불과 사람이 모두 이동을 하므로 두개를 둘 다 bfs를 돌려주었다. 각각의 큐를 만들었고 입력을 받으면서 불과 사람의 위치의 좌표를 각각의 큐에 담아주었다.

 

사람이 이동할 때 불이 번지려는 칸이면 사람은 이동을 하지 못하니까 먼저 불이 이동하고 다음에 사람이 이동한다. 이는 한 턴 즉 1초 동안 일어나므로 while(! personQ.isEmpty())이렇게 while문을 만들어준다.

 

먼저 불부터 bfs를 돌려주었다.

int fireQsize = fireQ.size();
for(int i = 0; i < fireQsize; i++)

 

이렇게 fireQ를 탐색했는데 한 턴에 fireQ에 저장되어 있는 불들의 다음 번지려는 위치를 파악하기 위해 이렇게 해주었다. fireQsize를 선언하지 않고 for문 종료 조건으로 fireQ.size()를 사용하거나 while(! fireQ.isEmpty())를 사용하면 한 턴에 해당하는 fireQ를 탐색하는 것이 아니기 때문에 위처럼 써주어야 한다.

 

그리고 빈 공간이면 불을 퍼뜨리고 해당 칸을 fireQ에 담아준다.

 

다음은 사람이 이동할 차례이다.

사람도 불이 이동하는 것과 똑같다. 일단 사람의 위치가 2차원 배열의 경계면에 위치한다면 탈출에 성공한것이므로 시간을 반환한다.

탈출을 하지 못했다면 동서남북을 돌면서 빈공간이고 방문하지 않은 곳이면 그 칸으로 이동하고 personQ에 담아준다.