[Java] 백준 5427번 : 불

1. 문제

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

5427번: 불

 

 

2. 풀이 과정

상근이가 이미 지나간 곳은 불이 번져도 상근이를 따라 잡을 수 없기 때문에, 불이 번지는 건 빈칸만 고려해주었다. 빈칸을 누가 먼저 가냐만 보면 된다.

 

상근이가 현재 갈 수 있는 위치와 불이 방금 번진 위치를 모두 queue에 넣고, 4방향 탐색으로 갈 수 있는 곳에 표시를 해준다. 이때, 상근이는 불이 다 번지고 난 후에 움직이기 때문에 처음 상근이의 위치는 queue의 마지막에 넣어주도록 해서 구현한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int w, h, result;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    static char[][] arr;
    static Queue<int[]> q;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for(int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            arr = new char[h][w];
            q = new LinkedList<>();
            result = 0;

            int x = 0, y = 0;

            for(int i = 0; i < h; i++) {
                String str = br.readLine();
                for(int j = 0; j < w; j++) {
                    arr[i][j] = str.charAt(j);
                    if(arr[i][j] == '*'){
                        q.add(new int[]{i, j});
                    }
                    else if(arr[i][j] == '@'){
                        x = i;
                        y = j;
                    }
                }
            }
            q.add(new int[]{x, y});
            sb.append(simulation() ? result : "IMPOSSIBLE").append("\n");
        }
        System.out.println(sb);
        br.close();
    }

    public static boolean simulation() {
        while(!q.isEmpty()){
            result++;
            for(int i=0, size = q.size(); i<size; i++){
                int[] now = q.poll();
                for(int j=0; j<4; j++){
                    int nx = now[0] + dx[j];
                    int ny = now[1] + dy[j];
                    if(nx < 0 || nx >= h || ny < 0 || ny >= w){
                        if(arr[now[0]][now[1]] == '@'){
                            return true;
                        }
                        continue;
                    }
                    if(arr[nx][ny] != '.'){continue;}
                    arr[nx][ny] = arr[now[0]][now[1]];
                    q.add(new int[]{nx, ny});
                }
            }
        }

        return false;
    }
}

 

 

결과