BOJ-5427-불
얼핏보면 일반 BFS와 같은 문제라고 생각이 들 수 있지만 곰곰히 생각해보다 보면 아차(?) 하는 문제다.
처음에는 사람이 BFS를 돌기 전에 맵에서 *을 찾아 확장시키는 식으로 구현해봤었는데 이는 매 번 맵을 다 탐색해서 *를 찾아야 하는 매우 비효율적인 방법이다. 역시나 시간초과ㅠㅠ
이 문제의 포인트는 BFS를 순회하는 녀석들이 여러 개 라는 점이다! 사람 BFS와 불 BFS를 번갈아 해주면 된다.
그렇다면 어떻게 번갈아 해줄것인가…? 이 부분에 대해 한참을 고민했었는데… 이게 바로 습관적인 코드 접근방식의 문제라고 생각한다.. 보통 BFS를 순회할 때 큐가 비어있지 않으면 계속 순회하도록 empty()함수를 사용해 구현한다. 하지만 이런식으로 하면 어떻게 번갈아 할 수 있지…? 라는 생각에 한참 고민을 했다.
방법은 비어있지 않을 때 까지가 아니라 현재 큐에 남아있는 개수만큼 반복시켜주면 되는 것!
여기까지 이해했다면 나머지는 기본적인 BFS문제를 풀듯이 풀어나갈 수 있다.
여러 번의 케이스가 있는 문제이기 때문에 각 케이스가 끝나고 초기화는 항상 필수!! 나와같이 queue나 vector를 전역으로 사용했다면 특히나 꼭 clear를 해줘야 한다. 항상 이 부분에서 틀리고 넘어가는듯하다..
여기서 Point는 내가 정의한 구조체다.
큐 클리어 1, 함수를 만들어 사용하기.
void clear( queue<Point> &q )
{
queue<Point> empty;
swap( q, empty );
}
queue<Point> q;
clear(q);
큐 클리어 2, 빌 때까지 pop하기
queue<Point> q;
...
while(!q.empty()) {
q.pop();
}
풀이보기
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int T, w, h;
char map[1001][1001];
int visited[1001][1001];
int mr[4] = { 1, -1, 0, 0 };
int mc[4] = { 0, 0, 1, -1 };
struct Point {
int y, x;
Point(int a, int b) {y = a; x = b;};
Point() {};
};
void clear( queue<Point> &q )
{
queue<Point> empty;
swap( q, empty );
}
vector<Point> fp;
queue<Point> q;
queue<Point> fq;
void bfs() {
for (int i=0; i<fp.size(); i++) {
fq.push(fp[i]);
}
while (!q.empty()) {
int fireSize = fq.size();
while (fireSize--) {
Point p = fq.front(); fq.pop();
for(int i=0; i<4; i++) {
int nr = p.y + mr[i];
int nc = p.x + mc[i];
if(nr<0 || nc<0 || nr>=h || nc>=w ) continue;
if(map[nr][nc] == '#') continue;
if(map[nr][nc] == '*') continue;
map[nr][nc] = '*';
fq.push(Point(nr, nc));
}
}
int qSize = q.size();
while (qSize--) {
Point p = q.front(); q.pop();
for(int i=0; i<4; i++) {
int nr = p.y + mr[i];
int nc = p.x + mc[i];
if(nr<0 || nc<0 || nr>=h || nc>=w) {
printf("%d\n", visited[p.y][p.x]+1);
return;
}
if(map[nr][nc] == '#') continue;
if(map[nr][nc] == '*') continue;
if(visited[nr][nc] != 0) continue;
visited[nr][nc] = visited[p.y][p.x] + 1;
q.push(Point(nr, nc));
}
}
}
printf("IMPOSSIBLE\n");
}
void reset() {
for(int i=0; i<h; i++) {
for(int j=0; j<w; j++) {
visited[i][j] = 0;
}
}
}
void cleared() {
clear(q);
clear(fq);
fp.clear();
}
int main(void) {
scanf("%d", &T);
while (T--) {
scanf("%d %d", &w, &h);
reset();
for(int i=0; i<h; i++) {
scanf("%s", map[i]);
for(int j=0; j<w; j++) {
if(map[i][j] == '@') {
q.push(Point(i, j));
}
else if(map[i][j] == '*') {
fp.push_back(Point(i, j));
}
}
}
bfs();
cleared();
}
return 0;
}
```
찾아보니 큐를 두 개 만들지 않고도 하나의 큐에 현재 지점, 불의 여부, 카운트 등을 엮은 구조체를 만들어 사용해서 구현하는 방법도 있었다.