백준 4179 불! / C++

문제 : 링크텍스트

풀이 point

지훈이와 불의 이동거리 값이 겹치면 안됨
불에 대한 bfs를 먼저 진행 후
지훈이를 움직임으로써 지훈이의 이동거리와 불의 이동거리를 비교하며 지훈이가 탈출 할 수 있는지를 비교

풀이 순서

1. 입력
2. 맵을 순회하면서 F를 만났을 때는 F큐에 push
3. J를 만났을 때는 J큐에 push
4. 불에 대한 bfs 진행
5. 지훈이에 대한 bfs 진행
   5-1. 이떄 지훈이의 이동거리가 불의 이동거리보다 크면 안됨(이미 불이 퍼진 후)
   5-2. 지훈이는 맵 바깥으로 나가면 탈출을 성공 함
6. 맵 바깥으로 나갔다면 최소 이동거리 출력(나가기 전 이동거리)
   나가지 못했다면 IMPOSSIBLE 출력

코드

//백준 4179, 불!

#include <iostream>
#include <vector>
#include <queue>
#define x first
#define y second

std::queue<std::pair<int, int>> fireQ;
std::queue<std::pair<int, int>> jihoonQ;
std::vector<int> dx = {1, 0, -1, 0};
std::vector<int> dy = {0, -1, 0, 1};

char grid[1000][1000];
int fdist[1000][1000];
int jdist[1000][1000];

int R, C;


void testprint(){
    std::cout << "--------------------------------------------" << '\n';
    for(int i{0}; i<C; ++i){
        for(int j{0}; j<R; ++j){
            std::cout << jdist[i][j] << ' ';
        }
        std::cout << '\n';
    }
}

void fireBfs(){
    while(!fireQ.empty()){
        auto curr = fireQ.front(); fireQ.pop();
        for(int k{0}; k<4; ++k){
            int nx = curr.x + dx[k];
            int ny = curr.y + dy[k];
            if(nx >= R || nx <0 || ny >= C || ny < 0) continue;
            if(grid[nx][ny] == '#') continue;
            if(fdist[nx][ny] > 0) continue;
            fdist[nx][ny] = fdist[curr.x][curr.y] + 1;
            fireQ.push({nx, ny});
        }
    }
}

void jihoonBfs(){
    while(!jihoonQ.empty()){
        auto curr = jihoonQ.front(); jihoonQ.pop();
        for(int k{0}; k<4; ++k){
            int nx = curr.x + dx[k];
            int ny = curr.y + dy[k];
            if(nx >= R || nx <0 || ny >= C || ny < 0){
                std::cout << jdist[curr.x][curr.y];
                return;
            }
            if(jdist[nx][ny] > 0) continue;
            if (fdist[nx][ny] != 0 && fdist[nx][ny] <= jdist[curr.x][curr.y] + 1) continue;
            if(grid[nx][ny] == '#') continue;
            jdist[nx][ny] = jdist[curr.x][curr.y] + 1;
            jihoonQ.push({nx, ny});
        }
    }
    std::cout << "IMPOSSIBLE";
}


int main(){
    
    std::cin >> R >> C;
    for(int i{0}; i<R; ++i){
        std::string row;
        std::cin >> row;
        for(int j{0}; j<C; ++j){
            grid[i][j] = row[j];
            if(grid[i][j] == 'J'){
                jihoonQ.push({i, j});
                jdist[i][j] = 1;
            }
            else if(grid[i][j] == 'F'){
                fireQ.push({i, j});
                fdist[i][j] = 1;
            }
        }  
    }

    fireBfs();
    jihoonBfs();

    //testprint();

    return 0;
}