[백준 5427번] 불 C++

www.acmicpc.net/problem/5427

5427번: 불

 

문제를 딱 보고 아 이건 무조건 bfs 문제다 라고 판단했는데

 

한번에 두 가지의 주체를 움직이는 bfs문제에 대한 경험이 없었어서 좀 고생했습니다.

 

불이 먼저 움직이고 불이 움직인자리를 visit 처리 한 후 상근이가 움직여서 

불이 닿은 자리는 상근이가 아예 가지 못 하게 구성했습니다.

 

불같은경우 초기에 한개만 존재하는게 아니라 다수의 위치에서 불이 존재할 수 있기 때문에

'*' 을 입력 받을때 미리 큐에다가 위치정보를 저장하여 탐색했습니다.

 

아 그리고 상근이의 탈출 조건에 대한 고민이 많았는데

정해진 배열 밖으로 나갈시 상근이가 무사히 탈출한 것으로 생각하면 쉽습니다

 

 

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int t, w, h;
char arr[1001][1001];
bool visit[1001][1001];
//'*' 과 '@' 의 위치정보를 저장하는 큐
queue<pair<int, int>> fireq;
queue<pair<int, int>> sangq;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int bfs() {
    int cnt = 0;
    //상근이 위치를 나타내는 queue가 빈다면 상근이는 갇혔거나 나갔거나 둘중 하나
    while (!sangq.empty()) {
        int fire = fireq.size();
        int sang = sangq.size();
        cnt++;
        //미리 넣어둔 fire큐에 있는 size번 반복 >> 즉 불이 몇 개든 가능한 모든 불을 한번씩 bfs탐색
        while (fire--) {
            int x = fireq.front().first;
            int y = fireq.front().second;
            fireq.pop();
 
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                //범위를 벗어나지않고, 아직 방문 전이며 '.' 인 곳을 탐색
                if (nx >= 0 && ny >= 0 && nx < h && ny < w && !visit[nx][ny] && arr[nx][ny] == '.') {
                    visit[nx][ny] = true;
                    fireq.push({ nx,ny });
                }
            }
        }
        while (sang--) {
            int x = sangq.front().first;
            int y = sangq.front().second;
            sangq.pop();
 
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                //상근이의 경우 정해진 배열을 이탈할 경우 탈출한것으로 봄
                if (nx < 0 || ny < 0 || nx >= h || ny >= w)
                    return cnt;
                if (nx >= 0 && ny >= 0 && nx < h && ny < w && !visit[nx][ny] && arr[nx][ny] == '.') {
                    visit[nx][ny] = true;
                    sangq.push({ nx,ny });
                }
            }
        }
    }
    return -1;
}
int main() {
    cin >> t;
    while (t--) {
        //테스트케이스마다 visit과 큐를 초기화
        memset(visit, false, sizeof(visit));
        while (!fireq.empty()) fireq.pop();
        while (!sangq.empty()) sangq.pop();
 
        cin >> w >> h;
        //불과 상근이의 위치를 전부 미리 큐에다가 저장
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++) {
                cin >> arr[i][j];
                if (arr[i][j] == '*') {
                    fireq.push({ i,j });
                    visit[i][j] = true;
                }
                else if (arr[i][j] == '@') {
                    sangq.push({ i,j });
                    visit[i][j] = true;
                }
            }
        int result = bfs();
        if (result == -1)
            cout << "IMPOSSIBLE" << '\n';
        else
            cout << result << '\n';
    }
    return 0;
}