백준 5427번 자바 : 불

분류

• 그래프 이론
• BFS

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 
    static int t, w, h;
    static char[][] map;
    static int[][] visited;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    static Queue<Pos> q, fire;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while(t-->0) {
            int w = sc.nextInt();
            int h = sc.nextInt();

            map = new char[h][w];
            visited = new int[h][w];
            for(int i=0; i<visited.length; i++) {
                Arrays.fill(visited[i], -1);
            }
            q = new LinkedList<>();
            fire = new LinkedList<>();
            boolean check = false;
            
            for(int i=0; i<h; i++) {
                String str = sc.next();
                for(int j=0; j<w; j++) {
                    map[i][j] = str.charAt(j);
                    if(map[i][j]=='*') {
                        fire.offer(new Pos(i,j));
                    }

                    if(map[i][j]=='@') {
                        q.offer(new Pos(i,j));
                        visited[i][j] = 0;
                    }
                }
            }

            out : while(true) {
                // 불 번짐
                int fSize = fire.size();
                for(int i=0; i<fSize; i++) {
                    Pos cur = fire.poll();
                    for(int dir = 0; dir < 4; dir++) {
                        int nx = cur.x + dx[dir];
                        int ny = cur.y + dy[dir];
                        if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                        if(map[nx][ny]=='#' || map[nx][ny]=='*') continue;
                        map[nx][ny] = '*';
                        fire.offer(new Pos(nx, ny));
                    }
                }

                // 상근 이동
                int qSize = q.size();
                for(int i=0; i<qSize; i++) {
                    Pos cur = q.peek(); q.poll();
                    for(int dir=0; dir<4; dir++) {
                        int nx = cur.x + dx[dir];
                        int ny = cur.y + dy[dir];
                        if(nx < 0 || nx >= h || ny < 0 || ny >= w) {
                            sb.append(visited[cur.x][cur.y] + 1 + "\n");
                            check = true;
                            break out;
                        }
                        if(visited[nx][ny]>=0 || map[nx][ny]=='#' || map[nx][ny]=='*') continue;
                        q.offer(new Pos(nx, ny));
                        visited[nx][ny] = visited[cur.x][cur.y] + 1;    
                    }
                }

                if(q.isEmpty()) break;
            }
            
            if(!check) sb.append("IMPOSSIBLE\n");

        }
        System.out.println(sb.toString());
    }

    static class Pos {
        int x;
        int y;
        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }


}