[백준/Baekjoon] 4179 불! C++ :: BFS

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

4179번: 불!

---

1. Logic

불의 위치를 담은 queue fire과 지훈이의 위치를 담은 jihun queue 두개를 가지고 풀이했다.

불이 위치한 곳은 애초에 지훈이가 가지 못하고 지훈이가 움직이더라도 불이 오면 안되기 때문에 불을 먼저 BFS를 돌려 움직여줬다. 이후 불이 없는곳에 지훈이를 BFS를 돌려 움직여주면 불이 있는곳을 제외하고 대피할 수 있다.

 

처음에는 queue 4개를 사용하여 얕은 복사를 통해 위치를 저장했지만 시간 초과가 나서 q를 두개로 사용하는 방법을 생각해냈다.

---

 

2. Code

 통과한 코드

#include<bits/stdc++.h>

using namespace std;

int n, m;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

char input[1001][1001];
bool vis[1001][1001];

queue<pair<int, int>> fire;
queue<pair<int, int>> jihun;

int BFS() {
    int escapeTime = 0;
    
    while(1) {
        bool jihunMoveCheck = false;

        int fireCur = fire.size();
        int jihunCur = jihun.size();

        for(int i = 0; i < fireCur; i++) {
            int fy = fire.front().first;
            int fx = fire.front().second;
            fire.pop();

            for(int i = 0; i < 4; i++) {
                int fnx = fx + dx[i];
                int fny = fy + dy[i];

                if(fnx < 0 || fnx >= m || fny < 0 || fny >= n) continue;
                if(vis[fny][fnx]) continue;
                if(input[fny][fnx] == '#') continue;

                vis[fny][fnx] = true;

                fire.push({fny, fnx});
            }
        }

        for(int i = 0; i < jihunCur; i++) {
            int jy = jihun.front().first;
            int jx = jihun.front().second;
            jihun.pop();
             for(int i = 0; i < 4; i++) {
                int jnx = jx + dx[i];
                int jny = jy + dy[i];

                if(jnx == m || jnx == -1 || jny == n || jny == -1) {
                    return escapeTime + 1;
                }
                if(vis[jny][jnx]) continue;
                if(input[jny][jnx] == '#') continue;
                if(input[jny][jnx] == 'F') continue;
                
                vis[jny][jnx] = true;

                jihun.push({jny, jnx});
                jihunMoveCheck = true;
            }
        }
        if(jihunMoveCheck) {
            escapeTime++;
        }
        else {
            return -1;
        }

    }

}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> input[i][j];

            if(input[i][j] == '#') {
                vis[i][j] = true;
            }
            else if(input[i][j] == 'J') {
                jihun.push({i, j});
                vis[i][j] = true;
            }
            else if(input[i][j] == 'F') {
                fire.push({i, j});
                vis[i][j] = true;
            }
        }
    }

    int res = BFS();

    if(res == -1) {
        cout << "IMPOSSIBLE";
    }
    else {
        cout << res;
    }
}

 

시간초과 난 코드 > queue 얕은 복사

#include<bits/stdc++.h>

using namespace std;

int n, m;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

char input[1001][1001];
bool vis[1001][1001];

queue<pair<int, int>> fire;
queue<pair<int, int>> jihun;

queue<pair<int, int>> tempFire;
queue<pair<int, int>> tempJihun;

int BFS() {
    int escapeTime = 0;
    
    while(1) {
        bool jihunMoveCheck = false;

        while(!fire.empty()) {
            int fy = fire.front().first;
            int fx = fire.front().second;
            fire.pop();

            for(int i = 0; i < 4; i++) {
                int fnx = fx + dx[i];
                int fny = fy + dy[i];

                if(fnx < 0 || fnx >= m || fny < 0 || fny >= n) continue;
                if(vis[fny][fnx]) continue;
                if(input[fny][fnx] == '#') continue;

                vis[fny][fnx] = true;

                tempFire.push({fny, fnx});
            }
        }

        while(!jihun.empty()) {
            int jy = jihun.front().first;
            int jx = jihun.front().second;
            jihun.pop();
             for(int i = 0; i < 4; i++) {
                int jnx = jx + dx[i];
                int jny = jy + dy[i];

                if(jnx == m || jnx == -1 || jny == n || jny == -1) {
                    return escapeTime + 1;
                }
                if(vis[jny][jnx]) continue;
                if(input[jny][jnx] == '#') continue;
                if(input[jny][jnx] == 'F') continue;
                
                vis[jny][jnx] = true;

                tempJihun.push({jny, jnx});
                jihunMoveCheck = true;
            }
        }
        if(jihunMoveCheck) {
            fire = tempFire;
            jihun = tempJihun;
            escapeTime++;
        }
        else {
            return -1;
        }

    }

}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> input[i][j];

            if(input[i][j] == '#') {
                vis[i][j] = true;
            }
            else if(input[i][j] == 'J') {
                jihun.push({i, j});
                vis[i][j] = true;
            }
            else if(input[i][j] == 'F') {
                fire.push({i, j});
                vis[i][j] = true;
            }
        }
    }

    int res = BFS();

    if(res == -1) {
        cout << "IMPOSSIBLE";
    }
    else {
        cout << res;
    }
}

 

---

3. Feedback

점점 골드 문제도 풀이 없이 내가 로직을 직접 구현해서 풀고 있다. 예전보다 실력이 점점 늘고있는 것 같아서 다행이고 뿌듯하다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐