[BOJ - 5427] 불

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

5427번: 불

 

빡구현 bfs, dfs 문제를 찾던 도중 난이도가 가장 낮아 보여서 선택한 문제

 

생각보다 어려웠고 시간이 오래걸렸다 ㅠㅠ

 

결국 질문검색 게시판에 있는 반례들을 활용해 푸는데 성공했다.

 

- 풀이 방법

1. 벽 밖에 지점을 -1로 표시해준다.(-1은 나중에 도착했을 때 도착 지점의 값이 됩니다.)

2. 입력을 받는다.

 - 벽 : -2

 - 사람, 불은 다른 맵에 표시해준다.

 

2. 만약 맵에 불이 없을 경우(처음에 이 조건을 고려하지 않았다...)

 - 최단 경로를 찾는다

 

3. 불이 있을 경우

 - fire_map에 일단 불은 먼저 퍼뜨려줍니다.

 - 그 다음 people_map에 1초가 지날 때마다 상근이가 갈 수 있는 지점을 표시해줍니다.

 - 불이 지나가지 않았거나 불이 이미 있는 곳은 상근이가 갈 수 없습니다.

   (이 조건을 잘 활용해 상근이가 이동할 수 있는 경로를 dist라는 배열에 -3을 넣어줍니다.)

 - 상근이의 위치를 큐에 넣고 bfs탐색으로 최단경로를 구해줍니다.

 

4. 답을 출력합니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>

using namespace std;

struct POINT {
	int y, x;
};
int t, w, h, ans;
int map[1002][1002];
int fire_map[1002][1002];
int people_map[1002][1002];
int dist[1002][1002];
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
queue<POINT> people, fire;
POINT p;

int main(void) {

	scanf("%d", &t);

	for (int tc = 1; tc <= t; tc++) {

		scanf("%d %d", &w, &h);

		for (int y = 0; y <= h + 1; y++) {
			map[y][0] = -1, map[y][w + 1];
			fire_map[y][0] = -1, fire_map[y][w + 1] = -1;
			people_map[y][0] = -1, people_map[y][w + 1] = -1;
			dist[y][0] = -1, dist[y][w + 1] = -1;
		}
	
		for (int x = 0; x <= w + 1; x++) {
			map[0][x] = -1, map[h + 1][x] = -1;
			fire_map[0][x] = -1, fire_map[h + 1][x] = -1;
			people_map[0][x] = -1, people_map[h + 1][x] = -1;
			dist[0][x] = -1, dist[h + 1][x] = -1;
		}

		for (int y = 1; y <= h; y++) {
			for (int x = 1; x <= w; x++) {
				char temp;
				scanf(" %c", &temp);
				if (temp == '#') {
					map[y][x] = -2;	//벽 : -2
					people_map[y][x] = -2, fire_map[y][x] = -2;
					dist[y][x] = -2;
				}
				else if (temp == '@') {
					p.y = y, p.x = x;
					people_map[y][x] = 1;
					people.push({ y,x });
				}
				else if (temp == '*') {
					fire.push({ y,x });
					fire_map[y][x] = 1;
				}
			}
		}
		bool flag = false;
		bool flag2 = false;
		if (fire.size() == 0) flag2 = true;

		if (flag2) {
			ans = 0x7fffffff;
			while (!people.empty()) {
				POINT cur = people.front();
				people.pop();

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

					if (next.y < 0 || next.y > h + 1 || next.x < 0 || next.x > w + 1) continue;
					if (people_map[next.y][next.x] == 0) {
						people_map[next.y][next.x] = people_map[cur.y][cur.x] + 1;
						people.push(next);
					}
					else if (people_map[next.y][next.x] == -1) {
						flag = true;
						ans = min(ans, people_map[cur.y][cur.x]);
					}
				}
			}
		}
		else {
			while (!fire.empty()) {
				POINT cur = fire.front();
				fire.pop();

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

					if (next.y <= 0 || next.y >= h + 1 || next.x <= 0 || next.x >= w + 1) continue;
					if (fire_map[next.y][next.x] == 0) {
						fire_map[next.y][next.x] = fire_map[cur.y][cur.x] + 1;
						fire.push(next);
					}
				}
			}

			while (!people.empty()) {
				POINT cur = people.front();
				people.pop();

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

					if (next.y <= 0 || next.y >= h + 1 || next.x <= 0 || next.x >= w + 1) continue;
					if (people_map[next.y][next.x] == 0) {
						people_map[next.y][next.x] = people_map[cur.y][cur.x] + 1;
						people.push(next);
					}
				}
			}

			for (int y = 1; y <= h; y++) {
				for (int x = 1; x <= w; x++) {
					if (people_map[y][x] < fire_map[y][x]) {
						dist[y][x] = -3;
					}
					else if (fire_map[y][x] == 0) {
						dist[y][x] = -3;
					}
				}
			}

			queue<POINT> q;
			q.push(p);
			dist[p.y][p.x] = 1;
			ans = 0x7fffffff;

			while (!q.empty()) {
				POINT cur = q.front();
				q.pop();

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

					if (next.y < 0 || next.y > h + 1 || next.x < 0 || next.x > w + 1) continue;
					if (dist[next.y][next.x] == -3) {
						dist[next.y][next.x] = dist[cur.y][cur.x] + 1;
						q.push(next);
					}
					else if (dist[next.y][next.x] == -1) {
						flag = true;
						ans = min(ans, dist[cur.y][cur.x]);
					}
				}
			}
		}

		if (flag) {
			printf("%d\n", ans);
		}
		else printf("IMPOSSIBLE\n");

		memset(dist, 0, sizeof(dist));
		memset(people_map, 0, sizeof(people_map));
		memset(fire_map, 0, sizeof(fire_map));
	}


	getchar();
	getchar();

	return 0;
}