[BOJ] 불

Posted on | In |

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

  • ’.’: 빈 공간
  • ’#’: 벽
  • ’@’: 상근이의 시작 위치
  • ‘*’: 불

각 지도에 @의 개수는 하나이다.

제한사항

이외의 제한사항은 없다.

첫번째 생각

간단한 BFS문제이다. 보통은 배열 범위를 벗어나면 이동하지 않지만, 배열범위를 벗어났다면

빌딩을 탈출했다고 생각하면 된다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution_5427_불 {
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1;tc<=T;tc++) {
			int w = sc.nextInt();
			int h = sc.nextInt();
			sc.nextLine();
			char[][] map = new char[h][w];
			boolean[][] firevisit = new boolean[h][w];
			boolean[][] visit = new boolean[h][w];
			Queue<Point> fire = new LinkedList<Point>();
			Queue<Point> q = new LinkedList<Point>();
			for(int y=0; y<h; y++) {
				map[y] = sc.nextLine().toCharArray();
				for(int x=0; x<w; x++) {
					if (map[y][x] == '*') {
						fire.add(new Point(x,y,0));
						firevisit[y][x] = true;
					} else if ( map[y][x] == '@') {
						q.add(new Point(x,y,1));
						visit[y][x] = true;
					}
				}
			}
			boolean escape = false;
			int ans = -1;
			while(!escape) {
				int fireSize = fire.size();
				for(int i=0; i<fireSize; i++) {
					Point p = fire.poll();
					for(int dir=0; dir<4; dir++) {
						int tempX = p.X + dx[dir];
						int tempY = p.Y + dy[dir];
						if ( InRange(tempX,tempY,h,w) ) {
							if ( !firevisit[tempY][tempX] && map[tempY][tempX] != '#') { // 아직 불이 번지지 않은 곳이라면
								firevisit[tempY][tempX] = true;
								fire.add(new Point(tempX,tempY,0));
							}
						}
					}
				}
				int Size = q.size();
				for (int i = 0; i < Size; i++) {
					Point p = q.poll();
					for (int dir = 0; dir < 4; dir++) {
						int tempX = p.X + dx[dir];
						int tempY = p.Y + dy[dir];
						if (InRange(tempX, tempY, h, w)) {
							if (!visit[tempY][tempX] && map[tempY][tempX] != '#' && !firevisit[tempY][tempX]) {
								visit[tempY][tempX] = true;
								q.add(new Point(tempX, tempY, p.T + 1));
							}
						} else { // 탈출했다.
							ans = p.T;
							escape = true;
						}
					}
				}
				if ( q.size() == 0 ) {
					escape = true;
				}
			}
			
			if ( ans == -1 ) System.out.println("IMPOSSIBLE");
			else System.out.println(ans);
			
			
		}
	}
	public static boolean InRange(int x,int y,int h,int w) {
		if ( x>=0 && y>=0 && x<w && y<h ) {
			return true;
		} return false;
	}
	
	public static class Point {
		int X;
		int Y;
		int T;
		Point(int x,int y,int t) {
			X=x;
			Y=y;
			T=t;
		}
	}
}