[BaekJoon] 백준 5427번 불

 

[BaekJoon] 백준 5427번 불

 

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

 

 

내코드

 

- 일단 이문제는 BFS에 기반한 문제다. 기존 bfs문제들과 조금 다르게 풀어야하기 때문에 알고나면 쉽지만 접근하기가 까다로운문제.

- BFS : Queue, 너비 우선, push할때 visited = true를 해줘야함

while(qu가 비어있지 않으면){
    1. pop()
    2. 인접 노드들 visited = false면 push
}

- 알고리즘

1. 테스트 케이스가 여러개이므로 사용하는 변수들을 매번 초기화 시켜준다.

2. bfs를 통해 불에 대한 맵을 만든다.(fireTime) 이때 pop을 통해 얻은 칸의 (time + 1)이 인접한 칸의 time보다 작다면 값을 갱신해준다.(따라서 처음에 초기화 시켜줄때 fireTime을 INF로 초기화 시켜줘야함) 왜냐하면 불이 더 빨리 번지는 지점이기 때문이다.

3. 불의 맵과 사람이 움직이는 것을 비교해 불보다 사람이 먼저 도착하는 곳으로 이동하며 탈출한다. 

 

#include <iostream>
#include <string>
#include <queue>
#include <utility>

using namespace std;

const int MAX = 1000;
const int INF = 2147438647;
int w, h;
int building[MAX][MAX];
queue<pair<int, int>> fire;
queue<pair<pair<int, int>, int>> person;
int fireTime[MAX][MAX];
bool visited[MAX][MAX];;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };

int movePerson() {
	while (!person.empty()) {
		int tmpx = person.front().first.first;
		int tmpy = person.front().first.second;
		int time = person.front().second;
		person.pop();
        // if person get out of building return time + 1
		if (tmpx == h - 1 || tmpx == 0 || tmpy == w - 1 || tmpy == 0) return time + 1;
		for (int i = 0; i < 4; i++) {
			int x = tmpx + dx[i];
			int y = tmpy + dy[i];
			if (x < 0 || y < 0 || x >= h || y >= w) continue;
			if (building[x][y] == 0 && visited[x][y] == false) {
				if (fireTime[x][y] > time + 1) {
					person.push(make_pair(make_pair(x, y), time + 1));
					visited[x][y] = true;
				}
			}
		}
	}
    // if person can't get out of building return -1
	return -1;
}

void getFireMap() {
	while (!fire.empty()) {
		int tmpx = fire.front().first;
		int tmpy = fire.front().second;
		fire.pop();
		for (int i = 0; i < 4; i++) {
			int x = tmpx + dx[i];
			int y = tmpy + dy[i];
			if (x < 0 || y < 0 || x >= h || y >= w) continue;
			if (building[x][y] != 1) {
				if (fireTime[x][y] > fireTime[tmpx][tmpy] + 1) {
					fireTime[x][y] = fireTime[tmpx][tmpy] + 1;
					fire.push(make_pair(x, y));
				}
			}
		}
	}
}

void initialize() {
	//initialize queue
	while (!fire.empty()) fire.pop();
	while (!person.empty()) person.pop();
	//initialize building and visited and fireTime
    for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			fireTime[i][j] = INF;
			visited[i][j] = false;
			building[i][j] = 0;
			char tmp;
			cin >> tmp;
			if (tmp == ',') building[i][j] = 0;
			else if (tmp == '#') building[i][j] = 1;
			else if (tmp == '@') {
				building[i][j] = 2;
				person.push(make_pair(make_pair(i, j), 0));
				visited[i][j] = true;
			}
			else if (tmp == '*') {
				building[i][j] = 3;
				fire.push(make_pair(i, j));
				fireTime[i][j] = 0;
			}
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T; cin >> T;
	while (T--) {
		cin >> w >> h;
		initialize();
		getFireMap();
		int result = movePerson();
		if (result == -1) cout << "IMPOSSIBLE" << "\n";
		else cout << result << "\n";
	}
	return 0;
}

 

참고