[BOJ/4179번불!] c++ / BFS

문제

지훈이가 미로에서 불을 피해 탈출할 수 있는지, 있다면 시간을 구하는 문제

불과 지훈은 상하좌우로 움직일 수 있고, 한번에 한칸씩만 움직일 수 있음

 

생각

토마토 문제처럼 큐 하나로 동시에 진행할 수 있을 거라 생각하고 코드를 짰는데 대실패함

예시가 별로 없어서 코드를 짜고도 맞는지 모르겠음 ㅠㅠ

도저히 못 풀겠어서 바킹독님 강의 봄

불 bfs랑 지훈이 bfs를 따로 만들어서 풀어야한다는 사실을 깨달음

 

문제풀이

1.불, 지훈이 vis 배열을 -1로 채우기 ( 거리를 초기화 시켜줌 ) - fill 함수 사용 ( fill(시작 위치, 끝 위치, 값) )

2.불 bfs 구하기 ( 기준 칸에서 +1 해주는 방식 )

-범위 벗어나면 continue

-방문했거나 #인 경우 continue

3.지훈이의 bfs 구하기 ( 기준 칸에서 +1 해주는 방식 )

-범위 벗어나면 최소 시간 출력하고 return

-방문했거나 #인 경우 continue

-불 vis가 -1이 아니고, 지훈 vis[cur.X][cur.Y]+1 이 불 vis 값보다 클 경우 continue

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define X first
#define Y second
string board[1001];
int Jvis[1001][1001], Fvis[1002][1002];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int R, C;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> R >> C;

    for ( int i = 0; i < R; i++ ) {
        fill(Fvis[i],Fvis[i]+C, -1);
        fill(Jvis[i],Jvis[i]+C, -1);
    }

    for ( int i = 0; i < R; i++ ) 
        cin >> board[i];
    
    queue<pair<int, int>> JQ, FQ;

    // 불이 나는 시간 구하기
    for ( int i = 0; i < R; i++ )
        for ( int j = 0; j < C; j++ ) {
            if ( board[i][j] == 'F' ) {
                FQ.push({i, j});
                Fvis[i][j] = 0;
            }
            else if ( board[i][j] == 'J') {
                JQ.push({i, j});
                Jvis[i][j] = 0;
            }
        }

    while ( !FQ.empty() ) {
        pair<int, int> cur = FQ.front(); FQ.pop();
        for ( int dir = 0; dir < 4; dir ++ ) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if ( nx < 0 || nx >= R || ny < 0 || ny >= C ) continue;
            if ( board[nx][ny] == '#' || Fvis[nx][ny] >= 0 ) continue;
            
            Fvis[nx][ny] = Fvis[cur.X][cur.Y] + 1;
            FQ.push({nx, ny});
        }
    }
    //지훈이가 탈출하는 시간 구하기
    while ( !JQ.empty() ) {
        pair<int, int> cur = JQ.front(); JQ.pop();
        for ( int dir = 0; dir < 4; dir ++ ) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if ( nx < 0 || nx >= R || ny < 0 || ny >= C ) {
                cout << Jvis[cur.X][cur.Y] + 1;
                return 0;
            }

            if ( board[nx][ny] == '#' || Jvis[nx][ny] >= 0 ) continue;
            if ( Fvis[nx][ny] != -1 && Fvis[nx][ny] <=  Jvis[cur.X][cur.Y] + 1 ) continue;
             Jvis[nx][ny] = Jvis[cur.X][cur.Y] + 1;
            JQ.push({nx, ny});
        }
    }

    cout << "IMPOSSIBLE";
    

   
}