#백준_5427 불 - Java 자바

# 유형 : 탐색, BFS

# 난이도 : 골드 IV

# 괜히 리스트도 쓰고 조건문 너무 구체적으로 하다가 메모리초과가 났다. 코드를 줄일 수 있는 만큼 줄이고, 불필요한 코드를 최대한 없애고 조건을 수정하니 정답이었다. 방법은 1) 불을 먼저 bfs를 통해 탐색해준다. 동시에 진행이라고 하지만 불이 번지는 곳에는 결국 상근이가 못움직이는 곳이기 때문에 불을 먼저 탐색해주고 그 다음 상근이의 움직임을 BFS를 통해 탐색한다.

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p5427 {
    static int R,C;
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static char arr[][];
    static boolean visit[][];
    static int map[][];
    static Queue<Point> fire;
    static Point start;
    static boolean isPossible;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());
        for(int tc=0; tc<testCases; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            C = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            isPossible = false;
            arr = new char[R][C];
            map = new int[R][C];
            fire = new LinkedList<>();
            
            for(int r=0; r<R; r++) {
                String str = br.readLine();
                for(int c=0; c<C; c++) {
                    char ch = str.charAt(c);
                    if(ch == '@')
                        start = new Point(c,r);
                    else if(ch == '*')
                        fire.add(new Point(c,r));
                    
                    arr[r][c] = ch;
                }
            }
            bfs();
            if(!isPossible) {
                System.out.println("IMPOSSIBLE");
            }
        }
    }
    
    public static void bfs() {
        Queue<Point> queue = new LinkedList<>();
        queue.add(start);
        
        while(!queue.isEmpty()) {
            int len = fire.size();
            for(int l=0; l<len; l++) {
                Point po = fire.poll();
                for(int d=0; d<4; d++) {
                    int newX = po.x + moveX[d];
                    int newY = po.y + moveY[d];
                    if(0<=newY && newY<R && 0<=newX && newX<C && arr[newY][newX]!='#' && arr[newY][newX]!='*') {
                        arr[newY][newX] = '*';
                        fire.add(new Point(newX,newY));
                    }
                }
            }
            
            len = queue.size();
            for(int l=0; l<len; l++) {
                Point po = queue.poll();
                if((po.x == 0) || (po.x == C-1) || (po.y == 0) || (po.y == R-1)) {
                    isPossible = true;
                    System.out.println(map[po.y][po.x] + 1);
                    return;
                }
                for(int d=0; d<4; d++) {
                    int newX = po.x + moveX[d];
                    int newY = po.y + moveY[d];
                    if(0<=newY && newY<R && 0<=newX && newX<C && arr[newY][newX]=='.'){
                        map[newY][newX] = map[po.y][po.x] + 1;
                        arr[newY][newX] = '@';
                        queue.add(new Point(newX,newY));
                    }
                }
            }
            
        }
        
    }
}