[백준] 5427번 : 불 (C++)

5427번 : 불

---

문제 )

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

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

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

 

 

입력 :

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

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

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

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

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

메모리와 시간을 더 절약할 수 있을 것 같다.  (예를 들면 vector를 사용하지 않는다거나, 초기화 부분을 다른것으로 대체하거나.)

 

#include <iostream>
#include <vector>
#include <queue>
#include <string>
 
 
using namespace std;
 
 
int t;
int w, h;
 
// 탈출 결과
bool result;
// 탈출했다면 최단 시간은?
int answer;
 
vector<vector<string>> vec;
vector<vector<int>> visited;
vector<pair<int, int>> fires;
pair<int, int> person;
 
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };
 
void bfs(pair<int, int> a)
{
 
    queue<pair<int, int>> q;
    // 상근이 위치 방문 처리 및 queue에 넣어주기
    int temp = 0;
    visited[person.first][person.second] = 1;
    q.push(make_pair(person.first, person.second));
 
    // 불이 있는 곳 방문처리 및 queue에 넣어주기
    for (int i = 0; i < fires.size(); i++)
    {
        int a = fires[i].first, b = fires[i].second;
        q.push(make_pair(a, b));
        visited[a][b] = 1;
    }
 
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            // 4방 탐색
            int x_dx = x + dx[i];
            int y_dy = y + dy[i];
 
            // 만약 지금 옮기는 것이 불이라면
            if (vec[x][y] == "*")
            {
                if ((-1 < x_dx && x_dx < h) &&                            // 1. 지도 밖으로 나가지 않고
                    (-1 < y_dy && y_dy < w) &&
                    (vec[x_dx][y_dy] == "." || vec[x_dx][y_dy] == "@"))    // 2. 방문할 곳이 빈 공간 or 상근
                {
                    // 이동한 곳은 불이 번진다.
                    q.push(make_pair(x_dx, y_dy));
                    vec[x_dx][y_dy] = "*";
                }
            }
            // 만약 지금 옮기는 것이 상근이라면
            else if (vec[x][y] == "@")
            {
                // 탈출에 성공했다면
                if ((-1 == x_dx || x_dx == h) ||
                    (-1 == y_dy || y_dy == w))
                {
                    // 성공처리
                    result = 1;
                    answer = visited[x][y];
                    return;
                }
 
                // 이동 중
                if ((-1 < x_dx && x_dx < h) &&        // 1. 지도 밖으로 나가지 않고
                    (-1 < y_dy && y_dy < w) &&
                    (visited[x_dx][y_dy] == 0) &&    // 2. 방문하지 않았고
                    (vec[x_dx][y_dy] == "."))        // 3. 이동 가능하다면
                {
                    q.push(make_pair(x_dx, y_dy));
                    vec[x_dx][y_dy] = "@";
                    visited[x_dx][y_dy] = visited[x][y] + 1;
                }
            }
        }
        
    }
 
}
 
int main()
{
    cin >> t;
 
    // 빌딩 지도 그리기
    for (int i = 0; i < t; i++)
    {
        cin >> w >> h;
 
        // 다음 테스트 케이스를 위해 초기화
        vec.clear();
        vec.resize(h);
        visited.clear();
        visited.assign(h, vector<int>(w, 0));
        fires.clear();
        result = 0;
        answer = 0;
 
        string object;
        for (int j = 0; j < h; j++)
        {
            cin >> object;
            int len = object.length();
            for (int k = 0; k < len; k++)
            {
                string temp = object.substr(k, 1);
                vec[j].push_back(temp);
 
                // temp가 상근이면
                if (temp == "@") person = make_pair(j, k);
                // temp가 불이라면 fires에 추가함
                else if (temp == "*") fires.push_back(make_pair(j, k));
            }
        }
 
        // 1. 불이 먼저 번짐.
        // 2. 이후에 상근이가 이동
        bfs(person);
 
        if (result)
        {
            cout << answer << "\n";
        }
        else 
        {
            cout << "IMPOSSIBLE\n";
        }
    }
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/5427 

5427번: 불