[BOJ] 불!

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이난 공간

J는 입력에서 하나만 주어진다.

풀이

4179

맞았습니다!!

5060

40

C++14 / 수정

2701

1분 전

 

1. 시뮬레이션

 

2. 큐를 두 개 생성한다. (지훈이큐, 불 큐)

 

3. 지훈이가 맵을 탈출하거나 (성공조건)

불과 벽에 막혀 오갈 때 없을 때(실패조건) 

반복해야 한다. (while(!jQ.empty()))

 

4. 불이 먼저 퍼지고 퍼진 불을 피해서 지훈이가 탈출한다. 

jQ에 원소가 있을 동안 불큐의 사이즈만큼 불을 상하좌우로 퍼지게 한다. 

 

그 후에 지훈이가 탈출한다. 만약 맵을 탈출하게 됐다면 그때의 시간을 출력하고 함수를 종료한다. 

탈출하지 못했다면 다시 큐에 넣어준다. 

 

---

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
//풀이 46분 
 
 
int r, c;
char map[1001][1001];
bool visited[1001][1001];
typedef pair<int, int> pp;
typedef pair<pp, int> ppp;
 
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
 
pp jihun;
vector<pp> fire;
 
void print()
{
    cout << '\n';
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cout << map[i][j] << ' ';
        }
        cout << '\n';
    }
    cout << '\n';
}
void bfs()
{
    queue<ppp> jQ;
    queue<pp> fireQ;
 
    for (auto f : fire)
    {
        fireQ.push(f);
    }
 
    jQ.push(ppp(pp(jihun.first, jihun.second), 0));
    visited[jihun.first][jihun.second];
 
    while (!jQ.empty())
    {
        int size = fireQ.size();
 
        while (size--)
        {
            int fx = fireQ.front().first;
            int fy = fireQ.front().second;
            fireQ.pop();
 
            for (int i = 0; i < 4; i++)
            {
                int fnx = fx + dx[i];
                int fny = fy + dy[i];
 
                if (fnx < 0 || fnx >= r || fny < 0 || fny >= c || map[fnx][fny] == '#' || map[fnx][fny] == 'F')
                    continue;
 
                map[fnx][fny] = 'F';
                fireQ.push(pp(fnx, fny));
            }
        }
        //while fire
 
        size = jQ.size();
 
         while (size--)
        {
            int x = jQ.front().first.first;
            int y = jQ.front().first.second;
            int cnt = jQ.front().second;
            jQ.pop();
 
            for (int i = 0; i < 4; i++)
            {
                //지훈스 움직임
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if (nx >= 0 && nx < r && ny >= 0 && ny < c)
                {
                    if (!visited[nx][ny] && map[nx][ny] == '.')
                    {
                        visited[nx][ny] = true;
                        jQ.push(ppp(pp(nx, ny), cnt + 1));
                    }
                }
                else
                {
                    cout << cnt + 1 << '\n';
                    return;
                }
            }
        }
    }
 
    cout << "IMPOSSIBLE" << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 'J')
            {
                jihun = pp(i, j);
            }
            else if (map[i][j] == 'F')
            {
                fire.push_back(pp(i, j));
            }
        }
    }
    //input
 
    bfs();
 
    return 0;
}