BOJ - 불(5437)

골드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;
}
 

Reference

• 백준(5437번) - 불