4179. 불! GOLD III( C++)

https://www.acmicpc.net/problem/4179

4179번: 불!

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

 

#include <iostream>
#include <queue>
#include <string.h>
 
using namespace std;
 
char MAP[1001][1001];
int mx[] = {-1,0,1,0}, my[] = {0,1,0,-1};
bool visit[1001][1001];
 
 
queue<pair<int, int> > f;
queue<pair<int, int> > j;
 
int n,m;
 
int solve(int jx, int jy)
{
    int num = 1;
    j.push({jx, jy});
 
    while(true)
    {
 
        int jsize = j.size();
        int fsize = f.size();
 
        while(fsize--)
        {
            int x = f.front().first;
            int y = f.front().second;
            f.pop();
 
            for(int i=0;i<4;i++)
            {
                int nx = x + mx[i];
                int ny = y + my[i];
 
                if(nx<0||ny<0||nx>=n||ny>=m || MAP[nx][ny] == 'F' || MAP[nx][ny] == '#') continue;
 
                MAP[nx][ny] = 'F';
                f.push({nx,ny});
 
            }
 
        }
        while(jsize--)
        {
            int x = j.front().first;
            int y = j.front().second;
            j.pop();
            if(x == 0 || y == 0 || x == n - 1 || y == m - 1)
            {
                return num;
            }
 
 
            for(int i=0;i<4;i++)
            {
                int nx = x + mx[i];
                int ny = y + my[i];
 
                if(nx<0||ny<0||nx>=n||ny>=m || visit[nx][ny] || MAP[nx][ny] == 'F' || MAP[nx][ny] == '#') continue;
 
                visit[nx][ny] = true;
                j.push({nx,ny});
 
 
            }
        }
        jsize = j.size();
        if(jsize == 0) return -1;
        num++;
    }
    return -1;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int jx,jy;
    string s;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        for(int j=0;j<m;j++)
        {
            MAP[i][j] = s[j];
            if(MAP[i][j] == 'F')
            {
                f.push({i,j});
                visit[i][j] = true;
            }
 
            else if(MAP[i][j] == 'J')
            {
                jx = i, jy = j;
                visit[i][j] = true;
            }
 
 
        }
    }
    int a = solve(jx, jy);
    if(a == -1)
        cout<<"IMPOSSIBLE\n";
    else
        cout<<a<<'\n';
    return 0;
}
 

저 num = 1에서 시작하는 것 때문에 계속 틀렸다 ㅎㅎㅎㅎㅎㅎㅎㅎ

 

1. 입력을 받으면서 불은 여러개일 수 있다. 그래서 불은 queue에 집어 넣어 준다.

2. bfs를 시작한다.

2 - 1 단계별로 수행하기 위해 while문 중첩을 사용했다. 

 

3. 같은 곳에 동시에 방문할 수 없기 때문에 불 먼저 확산을 시작한다. 불은 #이나 F인 곳 빼고 다 확산하면 된다.

4. 지훈이가 확산을 시작한다. 이 때 경계값에 도달하면 현재 거리를 리턴한다.

4 - 1. 지훈이는 이미 방문했던 노드나 불을 방문하지 못한다.