백준 4179 // 갈수있는지조사는 bfs visit 비교

4179번: 불! (acmicpc.net)

4179번: 불!

*팁

bfs는 main안에서 짜는게 낫다.

ret는 전역변수로?

 

 

* 아이디어

1. 불bfs => 불 도착시간들 모두 저장

2. 사람bfs :

종료조건 -> 그때v값이 답임.

----------------------------------

불보다 visit이 작다 -> 더빨리도착가능 -> 이동가능.

== visit(불) >= 사람 -> continue;

 

*예외처리

불이없는경우? visit(불) : 0 0 0 0 0 이렇게 됨

문제 : 불<사람 이므로 모두 갈수없게됨.

해결 : 초기화를 무한대(987654321)로 하면, 불>사람 이므로 모두갈수있는 곳으로 초기화.

즉, 초기화를 무한대로해서 => 초기값 : 모두갈수있음으로 설정.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int r,c,ret,vfire[1004][1004],vp[1004][1004],y,x;
//char a[54][54];
char a[1004][1004];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
queue<pair<int, int>> fq;
pair<int, int> J;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    queue<pair<int, int>> fq;
    
    /*
    * 예외처리 : 불이없는경우
    * 987654321이 아님 -> 방문한적잇음 -> pass
    */
    fill(&vfire[0][0], &vfire[0][0] + 1004 * 1004, 987654321);
    cin >>r>>c;
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            cin >> a[i][j];
            if (a[i][j] == 'J') {
                J.first = i, J.second = j;
            }
            if (a[i][j] == 'F') {
                //fire.push_back({ i,j });
                vfire[i][j] = 1;
                fq.push({ i,j });
            }
        }
    }
    //입력끝

    //초기 탈출조건
    /*if (J.first == 0 || J.first == r - 1 || J.second == 0 || J.second == c - 1)
    {
        cout << 0;
        return 0;
    }*/

    //1. 방화 방문배열 완성(최단거리저장됨)
    while (fq.size())
    {
        tie(y, x) = fq.front(); fq.pop();
        for (int i = 0; i < 4; ++i)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
            if (a[ny][nx] == '#') continue;
            if (vfire[ny][nx]!=987654321) continue;
            //if (a[ny][nx] == 'F') continue;
            //J.first = ny; J.second = nx;
            vfire[ny][nx] = vfire[y][x] + 1;
            fq.push({ ny,nx });
        }
    }
    /*for (pair<int, int> p : fire)
        if(!vfire[p.first][p.second]) bfsFire(p.first, p.second);*/

    //2. 지훈 방문배열 탐색
    queue<pair<int, int>> q;
    q.push({ J.first,J.second });
    vp[J.first][J.second] = 1;
    while (q.size())
    {
        tie(y, x) = q.front(); q.pop();
        if (y == 0 || y == r - 1 || x == 0 || x == c - 1)
        {
            ret = vp[y][x];
            break;
        }
        for (int i = 0; i < 4; ++i)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
            if (a[ny][nx] == '#') continue;
            if (vp[ny][nx]) continue;
            if (vp[y][x] + 1 >= vfire[ny][nx]) continue;
            //지훈<불->이동불가 / 역:지훈>=불
            //지훈+1 == 지훈이가 갈곳

            vp[ny][nx] = vp[y][x] + 1;
            q.push({ ny,nx });
        }
        //ret++;

    }

    if (ret != 0) cout << ret << "\n";
    else cout << "IMPOSSIBLE \n";
    return 0;

}