백준 4179 불! - C++

4179번: 불!

#include <iostream>
#include <queue>
using namespace std;

int r, c, jsx, jsy, ans;
char map[1000][1000];
int fire[1000][1000];
bool visit[1000][1000];
int goX[4] = { 0, 0, 1, -1 };
int goY[4] = { 1, -1, 0, 0 };
queue<pair<int, int>> fireq;

void Firemap(){
    while(!fireq.empty()){
        int qsize = fireq.size();
        for(int i = 0; i < qsize; i++){
            int curX = fireq.front().first;
            int curY = fireq.front().second;
            fireq.pop();

            for(int j = 0; j < 4; j++){
                int nextX = curX + goX[j];
                int nextY = curY + goY[j];

                if(nextX >= 0 && nextX < r && nextY >= 0 && nextY < c){
                    if(map[nextX][nextY] != '#'){
                        if(fire[nextX][nextY] > fire[curX][curY] + 1){
                            fire[nextX][nextY] = fire[curX][curY] + 1;
                            fireq.push(make_pair(nextX, nextY));
                        }
                    }
                }
            }
        }
    }
}

int Jihoon(){
    queue<pair<pair<int, int>, int>> q;
    q.push(make_pair(make_pair(jsx, jsy), 0));
    visit[jsx][jsy] = true;

    while(!q.empty()){
        int curX = q.front().first.first;
        int curY = q.front().first.second;
        int time = q.front().second;
        q.pop();

        if(curX == 0 || curX == r-1 || curY == 0 || curY == c-1)
            return time + 1;

        for(int i = 0; i < 4; i++){
            int nextX = curX + goX[i];
            int nextY = curY + goY[i];

            if(nextX >= 0 && nextX < r && nextY >= 0 && nextY < c){
                if(map[nextX][nextY] != '#' && visit[nextX][nextY] == false){
                    if(fire[nextX][nextY] > time + 1){
                        visit[nextX][nextY] = true;
                        q.push(make_pair(make_pair(nextX, nextY), time+1));
                    }
                }
            }
        }
    }
    return -1;
}

int main(){
    // 입력
    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') {
                jsx = i;
                jsy = j;
            }
            else if(map[i][j] == 'F') {
                fireq.push(make_pair(i, j));
                fire[i][j] = 0;
            } else
                fire[i][j] = 999999999;
        }
    }

    // 불 시간 구하기
    Firemap();

    // 지훈
    ans = Jihoon();

    if(ans == -1)
        cout << "IMPOSSIBLE" << '\n';
    else
        cout << ans << '\n';
    
}

---

 처음 보는 문제라 다른 곳에서 아이디어를 얻어와 문제를 풀이했습니다. 하도 고생을 해서 같은 유형인 경우 틀리지 않을 것 같네요.

 

1. 불이 어떻게 번질지 2차원 int 배열을 통해서 기록을 합니다.

    - 입력을 받을 때 fire큐에 push를 해주고 나중에 Firemap 함수를 통해서 불 번지는걸 시뮬레이션 하게 됩니다.

    - 이러면 2차원 int 배열에 해당 좌표에 '언제 불이 도착하는가' 가 저장되게 됩니다.

 

2. 이후 Jihoon 함수를 통해서 BFS를 진행하게 됩니다.

    - 대신 벽에는 갈 수 없고 1에서 구한 2차원 배열에 저장된 fire 도착 시간보다 빨라야 합니다. 이렇게 해야 지훈이 이동할 수 있습니다.

    - 이 때 추가로 visit 2차원 배열이 사용되게 되는데 이걸 하지 않으면 큐에 계속해서 4방향이 들어가게 되어서 메모리 초과가 발생합니다.

 

 위 2 조건을 이용하면 무난하게 풀 수 있는 문제였습니다. 대신 다른곳에서 아이디어를 얻어온거라 비슷한 유형의 문제들을 계속 풀면서 익숙해져야 겠습니다.