[백준][5427번]불[cpp, c++]

백준 5427번 불

• BFS + 시뮬레이션 문제이다.

• 이런 문제는 실수가 종종 나와서 시간을 많이 잡아먹는다.

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

• 풀이방법
  1) 최단 거리를 찾아야함으로 bfs를 쓴다.
  2) 불이 먼저 붙고, 사람이 먼저 움직인다.
  3) 불에 대한 bfs - > 사람에 대한 bfs를 사용한다.
  4) q의 사이즈를 이용하여 bfs 한다.

• 함수 설명
  1) input_data() : 입력 받는 함수 , 이때 큐에 값을 push 해주는 것이 중요하다. (시간 단축)
  2) bfs(): 불에 대한 bfs, 사람에 대한 bfs가 순차적으로 이뤄진다. 큐 사이즈를 이용해서 bfs를 진행시키면 되고, 사람bfs에서 범위를 나갔을 때 탈출한 것이라고 가정하면 된다.
  3) sol(): 초기화 + 답 출력, 테스트 케이스가 있음으로, 배열에 대한 초기화가 필요하다

 
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int nx[4] = { 1,0,-1,0 };
int ny[4] = { 0,1,0,-1 };
int w, h, T;
int flag;
int ans;
char build[1001][1001];
int check[1001][1001];
queue<pair<int, int>> fire_q;
queue<pair<int, int>> q;
void input_data() {  
    cin >> w >> h; 
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> build[i][j];
            if (build[i][j] == '*') {
                fire_q.push(make_pair(i, j));
            } 
            else if (build[i][j] == '@'){
                q.push(make_pair(i, j));
            } 
        }
    }
 
}
int bfs() {
 
    while (!q.empty()) {
        //불에 대한 bfs
        int len = fire_q.size();
        for (int k = 0; k < len; k++) {
            int x = fire_q.front().first;
            int y = fire_q.front().second;
            fire_q.pop();
            for (int i = 0; i < 4; i++) {
                int dx = x + nx[i];
                int dy = y + ny[i];
                if (dx >= h || dx < 0 || dy >= w || dy < 0) continue;
                if (build[dx][dy] == '.') {
                    build[dx][dy] = '*';
                    fire_q.push(make_pair(dx, dy));
                }
            }
        }
 
        int len2 = q.size();
        for(int k2=0; k2<len2; k2++){
            int tx = q.front().first;
            int ty = q.front().second;
            q.pop();
            if (tx == h - 1 || tx == 0 || ty == w - 1 || ty == 0) {
                return 1;
            }
            for (int i = 0; i < 4; i++) {
                int dx = tx + nx[i];
                int dy = ty + ny[i];
                if (dx >= h || dx < 0 || dy >= w || dy < 0) continue;
                if (check[dx][dy] == true) continue;
                if (build[dx][dy] != '.')continue;
                check[dx][dy] = true;
                q.push(make_pair(dx, dy));
            }
        }
        ans++;
    }
    return -1;
}
 
void sol() {
    cin >> T;
    while (T--) {
        //시작 
        input_data();
        int f1= bfs();
        if (f1==1) cout << ans+1 << "\n";
        else cout << "IMPOSSIBLE" << "\n";
        //초기화
        memset(check, 0, sizeof(check));
        memset(build, 0, sizeof(build));
        ans = 0;
        while (!q.empty()) q.pop();
        while (!fire_q.empty()) fire_q.pop();
    }
}
 
 
int main(void) {
    sol();
    return 0;
}