[Baekjoon]5427.불

5427.불

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

5427번: 불

---

3055.탈출과 거의 같은 문제였다. 다른 점은 이 문제에서는 도착지점이 맵에 주어져있지 않고 맵 밖으로 빠져나가야 탐색이 끝난다는 점이다. 

 

불이 번지는 것과 상근이가 이동하는것은 동시에 일어나기 때문에 불이 번질 예정인 곳으로는 상근이가 이동할 수 없다. 따라서 다음과 같이 접근했다.

1. 불이 먼저 번진다.
2. 불이 다 번지면 상근이가 이동한다.
3. 상근이가 맵 밖으로 나가면 종료한다.

불이 번지는 것과 상근이가 이동하는것을 한 번씩 진행하면서 상근이가 맵 밖으로 나가는지 확인한다. 보통 bfs를 할 때 큐에 아무것도 없을 때까지 탐색을 진행하지만 이번에는 한 번씩 번갈아가면서 탐색을 해야하므로 큐를 두개 생성하여 각각의 큐의 사이즈 만큼만 탐색을 반복하도록 한다. (fire : 불이 번질때 사용할 큐, start: 상근이가 이동할때 사용할 큐)

 

맵에서 벽이 주어지지만 어차피 벽이 있는 곳으로는 불이 번지지 못하고 상근이도 이동할 수 없기 때문에 굳이 건드리지 않아도 된다. 

 

상근이의 이동을 위해 탐색을 진행할 때 start큐가 비어있지 않으면 이동이 이루어진것이므로 step++ 을 수행한다. 

private static void spreadFire() {

		while (!fire.isEmpty() || !start.isEmpty()) {
			
			int fsize = fire.size();
			for (int i = 0; i < fsize; i++) { // 불 먼저 bfs. 현재 칸의 상하좌우만 탐색. 큐에 다음 칸이 들어있지만 상근이 이동후에 다시 bfs 수행. 
				Point p = fire.poll();
				int curX = p.x;
				int curY = p.y;

				for (int j = 0; j < 4; j++) {
					int nextX = curX + dx[j];
					int nextY = curY + dy[j];

					if (nextX >= 0 && nextY >= 0 && nextX < W && nextY < H) {
						if (map[nextY][nextX] == '.' || map[nextY][nextX] == '@') {
							map[nextY][nextX] = '*';
							fire.add(new Point(nextX, nextY));
						}
					}
				}
			}

			int ssize = start.size();
			if (ssize > 0) {
				step++;

				for (int i = 0; i < ssize; i++) { // 상근이 이동 bfs. 
					Point p = start.poll();
					int curX = p.x;
					int curY = p.y;

					for (int j = 0; j < 4; j++) {
						int nextX = curX + dx[j];
						int nextY = curY + dy[j];

						if (nextX < 0 || nextY < 0 || nextX >= W || nextY >= H) {
							flag = true;
							return;
						}
						if (map[nextY][nextX] == '.') {
							map[nextY][nextX] = '@';
							start.add(new Point(nextX, nextY));
						}

					}
				}
			} else {
				return;
			}
		}
	}

<전체코드>