[백준] 5427번 : 불

문제

 

 

접근 방식

4179번: 불!

위 문제에 조건이 좀 추가된 문제로

불이 붙은 칸뿐만 아니라 곧 불이 붙을 칸도 피해서 빌딩을 탈출해야 한다.

if (isVisited[x][y] || building[x][y] == '#') continue;
if (isFired[x][y] != 0 && isFired[x][y] - 1 < cur.time + 1) continue;

 

코드로 표현하면 위와 같은데 벽이거나 이미 방문한 곳은 패스하고

불이 났거나 불이 붙을 예정인 칸도 패스해야 한다.

 

탈출 여부는 이동한 칸의 좌표가 인덱스의 범위를 벗어난 경우로

이 때의 시간을 출력해주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());

		int[] dx = {1, -1, 0, 0};
		int[] dy = {0, 0, -1, 1};

		while (n-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");

			int w = Integer.parseInt(st.nextToken());
			int h = Integer.parseInt(st.nextToken());

			char[][] building = new char[h][w];

			boolean[][] isVisited = new boolean[h][w];
			int[][] isFired = new int[h][w];

			Queue<XY> sgs = new LinkedList<>();
			Queue<XY> fires = new LinkedList<>();

			XY sg;
			XY fire;

			for (int i = 0; i < h; i++) {
				char[] input = br.readLine().toCharArray();
				for (int j = 0; j < w; j++) {
					char c = input[j];
					if (c == '@') {
						sg = new XY(i, j, 1);
						sgs.offer(sg);
						isVisited[i][j] = true;
					} else if (c == '*') {
						fire = new XY(i, j, 1);
						fires.offer(fire);
						isFired[i][j] = 1;
					}
					building[i][j] = c;
				}
			}

			while (!fires.isEmpty()) {
				XY cur = fires.poll();

				for (int dir = 0; dir < 4; dir++) {
					int x = cur.x + dx[dir];
					int y = cur.y + dy[dir];

					if (x < 0 || x >= h || y < 0 || y >= w) continue;
					if (isFired[x][y] != 0 || building[x][y] == '#') continue;

					isFired[x][y] = cur.time + 1;
					fires.offer(new XY(x, y, cur.time + 1));
				}
			}

			boolean isPossible = false;

			out:
			while (!sgs.isEmpty()) {
				XY cur = sgs.poll();

				for (int dir = 0; dir < 4; dir++) {
					int x = cur.x + dx[dir];
					int y = cur.y + dy[dir];

					if (x < 0 || x >= h || y < 0 || y >= w) {
						sb.append(cur.time).append("\n");
						isPossible = true;
						break out;
					}
					if (isVisited[x][y] || building[x][y] == '#') continue;
					if (isFired[x][y] != 0 && isFired[x][y] - 1 < cur.time + 1) continue;

					isVisited[x][y] = true;
					sgs.offer(new XY(x, y, cur.time + 1));
				}
			}

			if (!isPossible) {
				sb.append("IMPOSSIBLE").append("\n");
			}
		}

		System.out.println(sb);
	}

	private static class XY {
		int x;
		int y;
		int time;

		public XY(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
}