[백준 BOJ] 5427 - 불

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

5427번: 불

입력

• 상근이의 위치와 불의 위치를 각각 큐에 저장하였다.
• 테스트 케이스가 있는 문제이므로, 테스트 케이스의 결과를 출력한 뒤 상근이의 위치가 저장되어있는 큐와 불의 위치가 저장되어 있는 큐를 초기화 시켜주었다. 또한 방문배열, 전체 배열도 초기화 시켰다.

구현 

• 상근이와 불은 동시에 번지고, 불이 번질 곳에는 상근이가 이동하지 못한다는 조건이 있기 때문에 불을 먼저 이동시켰다.
  • 원래는 불이 번질 위치만 저장해두고 상근이를 먼저 이동시켰는데 불필요한 작업이 들어가는 것으로 생각한다. 또한, 시간초과가 날 수 있다
• 불의 확산은 bfs 탐색을 사용하였다. 
  
  • 이때, 이미 불이 번진 곳에도 불을 확산시켰더니 시간초과가 났었다
• 상근이의 이동 또한 bfs 탐색을 사용하였다.(불의 확산과 똑같음)
  • 상근이가 이동하기 전, 탈출 조건을 먼저 확인하였다.
  • 탈출조건은 상근이가 map의 가장자리에 위치하면 탈출이다. 이때도 1초가 지나고 상근이가 이동하는 것이므로 출력 시 1을 더해주었다.
  • 상근이가 이동했다면, is_move 라는 flag 변수를 두어, 이동하지 못한 경우에는 IMPOSSIBLE를 출력할 수 있도록 하였다.

소스 코드

 

 

	#include<iostream>
	#include<queue>
	#include<string.h>
	#define endl "\n"
	#define MAX 1000
	using namespace std;
	struct INFO {
	bool visit; // 방문했는지
	bool next_fire; // 다음에 불 날 위치인가
	};
	int t;
	int w, h;
	int result; // 정답
	bool visit[MAX][MAX];
	char map[MAX][MAX];
	//INFO visit[MAX][MAX];
	deque<pair<int, int>>sang;// 상근이의 위치
	queue<pair<int, int>>fire;// 불의 위치
	int dy[4] = { 0,0,1,-1 };
	int dx[4] = { 1,-1,0,0 };
	void ptr() {
	for (int i = 0; i < h; i++) {
	for (int j = 0; j < w; j++) {
	cout << map[i][j] << ' ';
	}
	cout << endl;
	}
	cout << "=============" << endl;
	}
	void bfs() {
	while(!sang.empty()) {
	// 불 확산, 위치 저장
	bool is_move = false;
	int fire_size = fire.size();
	for (int i = 0; i < fire_size; i++) {
	int fire_y = fire.front().first;
	int fire_x = fire.front().second;
	fire.pop();
	for (int k = 0; k < 4; k++) {
	int fire_ny = fire_y + dy[k];
	int fire_nx = fire_x + dx[k];
	if (0 > fire_ny || fire_ny >= h || 0 > fire_nx || fire_nx >= w) continue;
	if (map[fire_ny][fire_nx] != '#' && map[fire_ny][fire_nx] != '*') { // 벽이 아니라면 불이 붙는다
	map[fire_ny][fire_nx] = '*';
	fire.push({ fire_ny,fire_nx }); // 새롭게 확산된 불의 위치 저장
	}
	}
	}
	// 상근이 이동, 위치 저장
	int sang_size = sang.size();
	for (int i = 0; i < sang_size; i++) {
	int y = sang.front().first;
	int x = sang.front().second;
	visit[y][x] = true;
	sang.pop_front();
	if (y == 0 || y == h - 1 || x == 0 || x == w - 1) {
	cout << result + 1 << endl;
	return;
	}
	for (int k = 0; k < 4; k++) {
	int ny = y + dy[k];
	int nx = x + dx[k];
	if (0 > ny || ny >= h || 0 > nx || nx >= w) continue; // 진행방향이 범위 초과
	if (map[ny][nx] == '#' || map[ny][nx] == '*' || visit[ny][nx] == true) continue; // 진행방향이 벽, 불, 방문했던 위치
	map[ny][nx] = '@';
	sang.push_back({ ny,nx });
	is_move = true;
	visit[ny][nx] = true;
	}
	}
	result++;
	if (!is_move) {
	cout << "IMPOSSIBLE" << endl;
	return;
	}
	}
	}
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--) {
	result = 0;
	cin >> w >> h;
	for (int i = 0; i < h; i++) {
	string str;
	cin >> str;
	for (int j = 0; j < w; j++) {
	map[i][j] = str[j];
	if (str[j] == '@') {
	sang.push_back({ i,j });
	}
	else if (str[j] == '*') {
	fire.push({ i,j });
	}
	}
	}
	bfs();
	// 초기화
	while (!sang.empty())sang.pop_front();
	while (!fire.empty())fire.pop();
	memset(visit, false, sizeof(visit));
	memset(map, '#', sizeof(map));
	}
	}

view raw 불.cpp hosted with ❤ by GitHub