이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 99 번째 글 입니다.
목차
골드4 : bfs 문제이다.
생각
단순한 구현 문제이다. 이 때, 순서를 잘 파악하는 것이 중요하다. 먼저, 불을 번지게 한 상태에서, 사람의 현재 위치로 부터 어디로 가는 것이 좋은지를 판단해야 한다. 그리고 사람이 가장 자리에 도착한다면, 다음번째에 탈출이 가능하다.
Code
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <string.h>
using namespace std;
// BFS를 사용하여 불을 붙인다.
// 불을 붙이는 행위는 언제 까지 하면 돼? -> 탈출하면 불 안붙여도 돼
// 그렇다면 사람이 움직이는 것에 불을 붙이는 행위는 의존적
// 그럼 q를 하나만 사용하면 될까?
// 아니야 불은 따로 움직여야해
// 이렇게 하자. 불의 시작 위치를 가지고 있는 q, 사람의 시작 위치를 가지고 있는 q를 두개를 만들자.
// 그리고 사람 q안이 비어있을 때까지 루프를 돌리는데, 그때 불 q를 돌리자.
const int MAX = 1000;
struct Dir{
int y;
int x;
};
Dir moveDir[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int W, H;
string graph[MAX];
bool visited[MAX][MAX];
pair<int, int> start;
vector<pair<int, int>> fire;
void printG(){
for (int i = 0; i < H; i++) {
cout << graph[i] << '\n';
}
cout << '\n';
}
int BFS(){
int ans = 0;
queue<pair<int, int>> q;
queue<pair<int, int>> fire_q;
q.push(start);
for (int i = 0; i < int(fire.size()); i++) {
fire_q.push(fire[i]);
}
while (!q.empty()) {
// 불을 먼저 붙인다.
int fireSize = int(fire_q.size());
for (int i = 0; i < fireSize; i++) {
int y = fire_q.front().first;
int x = fire_q.front().second;
fire_q.pop();
for (int j = 0; j < 4; j++) {
int nextY = y + moveDir[j].y;
int nextX = x + moveDir[j].x;
if (0 <= nextY && nextY < H && 0 <= nextX && nextX < W){
if (graph[nextY][nextX] == '.') {
graph[nextY][nextX] ='*';
fire_q.push(make_pair(nextY, nextX));
}
}
}
}
// printG();
// 사람을 이동시킨다.
int manSize = int(q.size()); // 와 이거 안해주면 q가 동적으로 크기가 바뀌어서 이상하게됨..
for (int i = 0; i < manSize; i++) {
int y = q.front().first;
int x = q.front().second;
q.pop();
// 가장 자리에 있을 경우에는 다음번에 탈출이다.
if (y == 0 || y == H-1 || x == 0 || x == W-1)
return ans + 1;
for (int i = 0; i < 4; i++) {
int nextY = y + moveDir[i].y;
int nextX = x + moveDir[i].x;
if (0 <= nextY && nextY < H && 0 <= nextX && nextX < W){
if (visited[nextY][nextX] == false && graph[nextY][nextX] != '*' && graph[nextY][nextX] != '#') {
visited[nextY][nextX] = true;
q.push(make_pair(nextY, nextX));
}
}
}
}
ans++;
// printG();
}
return -1;
}
int main(){
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
// tc 문제에서는 배열을 초기화 해주는 것을 까먹으면 안된다.
fire.clear();
memset(visited, false, sizeof(visited));
cin >> W >> H;
for (int i = 0; i < H; i++) {
cin >> graph[i];
for (int j = 0; j < W; j++) {
if (graph[i][j] == '@') {
start = make_pair(i, j);
visited[i][j] = true;
}
else if (graph[i][j] == '*') fire.push_back(make_pair(i, j));
}
}
int ans = BFS();
if (ans == -1) cout << "IMPOSSIBLE" << '\n';
else cout << ans << '\n';
}
return 0;
}