C++ / 백준 / 5427 / 불

문제

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

5427번: 불

문제풀이

불이 먼저 번지고 상근이가 움직이는 문제이다.

테스트 케이스가 있기 때문에 테스트 케이스를 돌리기 전에 초기화하는 함수를 따로 만든다.

불이 번지는 함수와 상근이가 움직이는 함수도 따로 만든다.

BFS로 문제를 풀었고 입력을 받을 때 시작 위치는 loc큐에, 불의 위치는 fire큐에 y, x좌표값을 입력한다.

void Init(int w, int h)

건물의 상태를 map이라는 2차원 벡터, loc큐, fire큐, 방문 여부를 알려주는 visit벡터를 전역 변수로 선언한다.

loc 큐와 fire 큐는 벡터로 이루어진 큐이다.

y좌표, x좌표, 몇 초가 지났는지를 알려주는 3개의 인덱스로 구성한다.

1초가 지났는지를 체크하기 위해 이전 초인 pre, f_pre, 현재 초인 cnt, f_cnt라는 변수를 선언한다.

 

void burn(int w, int h) {
	int idx(0);
	while (!fire.empty()) {
		int f_y = fire.front()[0];
		int f_x = fire.front()[1];
		f_cnt = fire.front()[2];
		if (f_pre != f_cnt) break;
		fire.pop();
		for (idx = 0; idx < 4; ++idx) {
			int n_y = f_y + dy[idx];
			int n_x = f_x + dx[idx];
			if (n_y >= 0 && n_y < h && n_x >= 0 && n_x < w) {
				if (map[n_y][n_x] == '.') {
					map[n_y][n_x] = '*';
					fire.push({ n_y,n_x,f_cnt + 1 });
				}
			}
		}
	}
	f_pre = f_cnt;
}

다음은 불이 번지는 것을 체크하기 위한 burn 함수이다.

while문은 fire큐가 비거나, 1초가 지나면 더 이상 실행하지 않는다.

불이 있는 칸에서 상하좌우로 움직일 때 범위 안에 들고, 해당 칸이 빈칸인 .일 때만 불 칸으로 바꾼다.

그리고 fire큐에 좌표와 초+1을 하여 값을 입력한다.

while문이 끝나면 burn함수가 끝나므로 상근이의 이동이 남아있어 또 burn함수를 실행할 수 있으므로 f_pre값을 f_cnt로 변경한다.

 

bool move(int w, int h) {
	bool esc(false);
	int idx(0);
	int y(0), x(0);
	while (!loc.empty()) { // 이동				
		y = loc.front()[0];
		x = loc.front()[1];
		cnt = loc.front()[2];
		if (pre != cnt) break;
		loc.pop();
		for (idx = 0; idx < 4; ++idx) {
			int n_y(y + dy[idx]);
			int n_x(x + dx[idx]);
			if (n_y >= 0 && n_y < h && n_x >= 0 && n_x < w) {
				if (!visit[n_y][n_x]) {
					if (map[n_y][n_x] == '.') {
						visit[n_y][n_x] = true;
						loc.push({ n_y,n_x,cnt + 1 });
					}
				}
			}
			else {
				cout << cnt + 1 << '\n';
				return true;
			}
		}
	}
	pre = cnt;
	return false;
}

move함수이다.

burn함수와 비슷하지만 조금 다르다.

방문 여부를 체크하여 같은 곳을 방문 못하도록 하고, 범위를 넘어 탈출을 했는지 알려주는 값을 return 한다.

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

vector<vector<char>>map;
queue<vector<int>>loc;
queue<vector<int>>fire;
vector<vector<bool>>visit;

int pre;
int cnt;
int f_pre;
int f_cnt;

void Init(int w, int h) {
	map = vector<vector<char>>(h, vector<char>(w, ' '));
	loc = queue<vector<int>>();
	fire = queue<vector<int>>();
	visit = vector<vector<bool>>(h, vector<bool>(w, false));
	pre = 0;
	cnt = 0;
	f_pre = 0;
	f_cnt = 0;
}

void burn(int w, int h) {
	int idx(0);
	while (!fire.empty()) {
		int f_y = fire.front()[0];
		int f_x = fire.front()[1];
		f_cnt = fire.front()[2];
		if (f_pre != f_cnt) break;
		fire.pop();
		for (idx = 0; idx < 4; ++idx) {
			int n_y = f_y + dy[idx];
			int n_x = f_x + dx[idx];
			if (n_y >= 0 && n_y < h && n_x >= 0 && n_x < w) {
				if (map[n_y][n_x] == '.') {
					map[n_y][n_x] = '*';
					fire.push({ n_y,n_x,f_cnt + 1 });
				}
			}
		}
	}
	f_pre = f_cnt;
}

bool move(int w, int h) {
	bool esc(false);
	int idx(0);
	int y(0), x(0);
	while (!loc.empty()) { // 이동				
		y = loc.front()[0];
		x = loc.front()[1];
		cnt = loc.front()[2];
		if (pre != cnt) break;
		loc.pop();
		for (idx = 0; idx < 4; ++idx) {
			int n_y(y + dy[idx]);
			int n_x(x + dx[idx]);
			if (n_y >= 0 && n_y < h && n_x >= 0 && n_x < w) {
				if (!visit[n_y][n_x]) {
					if (map[n_y][n_x] == '.') {
						visit[n_y][n_x] = true;
						loc.push({ n_y,n_x,cnt + 1 });
					}
				}
			}
			else {
				cout << cnt + 1 << '\n';
				return true;
			}
		}
	}
	pre = cnt;
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int y(0), x(0);
	int T(0);
	int w(0), h(0);

	cin >> T;

	while (T--) {
		bool esc(false);
		cin >> w >> h;
		Init(w, h);

		for (y = 0; y < h; ++y) {
			for (x = 0; x < w; ++x) {
				cin >> map[y][x];
				if (map[y][x] == '@') {
					loc.push({ y,x,0 });
					visit[y][x] = true;
				}
				else if (map[y][x] == '*')
					fire.push({ y,x,0 });
			}
		}

		while (1) {
			burn(w, h);
			esc = move(w, h);
			if (esc) break;
			else if (loc.empty()) {
				cout << "IMPOSSIBLE\n";
				break;
			}
		}
	}
}