[백준] 5427. 불 (Java)

 

🔒 문제

5427번: 불

 

 

🔑 알고리즘

BFS, 우선순위 큐

 

 

 

💡  풀이

1초마다  상근이와 불 모두 움직이기 때문에 둘의 상태를 모두 관리해주어야하고,

이제 불이 붙으려는 칸으로 상근이가 이동할 수 없다 (= 불이 상근이보다 먼저 움직인다라)는 조건이 있으므로

우선순위 큐를 이용한 BFS로 문제를 해결했다.

 

우선순위 큐의 기준을 시간이 빠른 순, 시간이 같다면 type이 낮은 순으로 설정하였고

불은 type을 0으로, 상근이는 type을 1로 설정하여 불이 더 먼저 처리될 수 있게 하였다.

 

*3055번 문제와 거의 동일한 것 같다.

 

✏️ 코드

package baekjoon.m9;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

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

	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());

		label1: for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int w = Integer.parseInt(st.nextToken());
			int h = Integer.parseInt(st.nextToken());
			boolean[][] visited = new boolean[h][w];

			PriorityQueue<Obj> pq = new PriorityQueue<>();
			for (int i = 0; i < h; i++) {
				String str = br.readLine();
				for (int j = 0; j < w; j++) {
					char c = str.charAt(j);

					if (c == '@') pq.add(new Obj(i, j, 1, 1));
					else if (c == '*') pq.add(new Obj(i, j, 1, 0));

					if (c != '.') visited[i][j] = true;
				}
			}

			while (!pq.isEmpty()) {
				Obj cur = pq.poll();

				if (cur.type == 1 && (cur.y == 0 || cur.y == h - 1 || cur.x == 0 || cur.x == w - 1)) {
					sb.append(cur.time).append("\n");
					continue label1;
				}

				for (int i = 0; i < dy.length; i++) {
					int ny = cur.y + dy[i];
					int nx = cur.x + dx[i];

					if (ny < 0 || ny >= h || nx < 0 || nx >= w || visited[ny][nx])
						continue;

					visited[ny][nx] = true;
					pq.add(new Obj(ny, nx, cur.time + 1, cur.type));
				}
			}

			sb.append("IMPOSSIBLE\n");
		}

		System.out.println(sb);
	}

	static class Obj implements Comparable<Obj> {
		int y, x, time, type;

		// type: 불(0), 상근(1)
		public Obj(int y, int x, int time, int type) {
			this.y = y;
			this.x = x;
			this.time = time;
			this.type = type;
		}

		@Override
		public int compareTo(Obj o) {
			return time == o.time ? type - o.type : time - o.time;
		}
	}
}