[BOJ] 불

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

 

풀이

 

5427

맞았습니다!!

6112

60

C++14 / 수정

2990

52초 전

 

1) bfs 문제

 

2) 불과 사람이 동시에 퍼지고 움직이기 때문에 큐를 두 개 사용한다. (불큐, 사람큐)

 

3) while반복문에 넣어놓고 사람큐가 비거나(불과 벽에 막혀서 움직일 수 없는 상태), 탈출하면 (맵 밖으로 나옴) 종료한다. 

 

4) while안에서는 시간을 계속 증가시킨다. 

 

5) spreadFire() 는 bfs로 불을 번지게 한다. (맵 현재 위치가 '.' 이거나 '@'인 경우)

movemove()는 상근이의 탈출을 돕는다. (단, 상근이가 맵 밖으로 가게 되면 -맵의 범위를 벗어나면- true를 반환해서 맵을 탈출했음을 알린다.)

큐를 한 바퀴 돌 때까지 탈출하지 못했으면 false를 반환한다.

 

6) 만약, 상근이가 더 이상 움직일 수 없어서 반복문을 빠져나왔다면 IMPOSSIBLE을 츌력하고 아니면 time을 출력한다. (불가능 스펠링 틀려서 틀리면 너무 아쉬우니 제출하기 전에 꼭 확인!)

 

---

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
 
char map[1002][1002];
int w, h;
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
bool visited[1002][1002];
 
typedef pair<int, int> pp;
queue<pp> person, fire;
 
void printMap()
{
    cout << '\n';
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cout << map[i][j] << " ";
        }
        cout << '\n';
    }
    cout << '\n';
}
void spreadFire()
{
    //불을 퍼트림
    int n = fire.size();
    while(n > 0) {
        int x = fire.front().first;
        int y = fire.front().second;
        fire.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < 0 || nx >= h || ny < 0 || ny >= w)
                continue;
 
            if (map[nx][ny] == '.' || map[nx][ny] == '@')
            {
                map[nx][ny] = '*';
                fire.push(pp(nx, ny));
            }
        }
        n--;
    }
}
bool movemove()
{
    int n = person.size();
    while(n--){
        pp now = person.front();
        person.pop();
 
        int x = now.first;
        int y = now.second;
 
        visited[x][y] = true;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < 0 || nx >= h || ny < 0 || ny >= w)
                return true;
 
            if (visited[nx][ny])
                continue;
 
            if (map[nx][ny] == '.')
            {
                map[nx][ny] = '@';
                person.push(pp(nx, ny));
            }
        }
    }
    return false;
}
void init()
{
    memset(map, 0, sizeof(map));
    memset(visited, false, sizeof(visited));
    w = 0;
    h = 0;
    while(!fire.empty()) fire.pop();
    while(!person.empty()) person.pop();
 
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++)
    {
        init();
 
        cin >> w >> h;
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                cin >> map[i][j];
                if (map[i][j] == '@')
                {
                    //ㅅㅏㅇ근이의 위치
                    person.push(pp(i, j));
                }
                else if (map[i][j] == '*')
                {
                    fire.push(pp(i, j));
                }
            }
        }
 
        int time = 0;
        bool flag = false;
        while (1)
        {
            time++;
            
            if (person.size() == 0) {
                flag = true;
                break;
            }
            spreadFire();
            if (movemove())
            {
                //지도 밖으로 탈출하면 끝 
                break;
            }
        }
        if (flag)
            cout << "IMPOSSIBLE" << '\n';
        else
            cout << time << '\n';
    }
    return 0;
}