내 코드
package com.company;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static char[][] arr;
static int w, h, time;
static Queue<int[]> fireQ = new LinkedList<>();
static PriorityQueue<Node> pq = new PriorityQueue<>();
static int[][] way = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static boolean[][] visited;
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
for (int tc = 0; tc < T; tc++) {
boolean check = false;
fireQ.clear();
pq.clear();
st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
time = 0;
arr = new char[h + 2][w + 2];
visited = new boolean[h + 2][w + 2];
for (int i = 1; i <= h; i++) {
String s = br.readLine();
for (int j = 1; j <= w; j++) {
arr[i][j] = s.charAt(j - 1);
if (arr[i][j] == '*') {
fireQ.add(new int[]{i, j});
}
if (arr[i][j] == '@')
pq.add(new Node(i, j, 0));
}
}
while (!pq.isEmpty()) {
Node node = pq.poll();
if (visited[node.x][node.y] || arr[node.x][node.y] == '*')
continue;
visited[node.x][node.y] = true;
if (node.x == 0 || node.y == 0 || node.x == h + 1 || node.y == w + 1) {
check = true;
time = node.dis;
break;
}
if (time == node.dis) {
fire(fireQ.size());
time++;
}
for (int i = 0; i < 4; i++) {
int x = node.x + way[i][0];
int y = node.y + way[i][1];
if (!visited[x][y] && arr[x][y] != '#' && arr[x][y] != '*') {
pq.add(new Node(x, y, node.dis + 1));
arr[x][y] = '@';
}
}
}
if (check)
System.out.println(time);
else
System.out.println("IMPOSSIBLE");
}
}
static void fire(int size) {
for (int i = 0; i < size; i++) {
int[] index = fireQ.poll();
for (int j = 0; j < 4; j++) {
int x = index[0] + way[j][0];
int y = index[1] + way[j][1];
if (x >= 1 && x < h + 1 && y >= 1 && y < w + 1 && arr[x][y] != '#' && arr[x][y] != '*') {
arr[x][y] = '*';
fireQ.add(new int[]{x, y});
}
}
}
}
}
class Node implements Comparable<Node> {
int x, y, dis;
public Node(int x, int y, int dis) {
this.x = x;
this.y = y;
this.dis = dis;
}
@Override
public int compareTo(Node o) {
return dis - o.dis;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
소수상수근 - 9421번 (0) | 2022.02.07 |
---|---|
스카이라인 쉬운거 - 1863번 (0) | 2022.02.04 |
월드컵 - 6987번 (0) | 2022.01.24 |
간선 이어가기2 - 14284번 (0) | 2022.01.21 |
백양로 브레이크 - 11562번 (0) | 2022.01.19 |