BOJ 2573: 빙산

백윤재·2021년 9월 13일

BFS boj cpp ps

BOJ

목록 보기

9/28

✔ 문제 링크

BOJ 2573: 빙산

✔ 문제해결전략

그래프 탐색

BFS(Breadth First Search)

✔ 해결과정

처음에 한 번의 BFS 사이클 내에 모든 것을 해결하려고 했는데 잘되지 않아서 헤맸다. 생각해 보면 처음에 빙산이 녹는 것에 대해 map을 업데이트하기 위해 한 사이클을 돌리고, 업데이트된 map에 대해 빙산 개수를 구하기 위해 두 번째 사이클을 돌려도 BFS 한 사이클 돌린 거랑 시간 복잡도가 같다.

그리고 map을 업데이트하는 과정에서 먼저 방문한 점이 업데이트되어 버리면 그 결과가 인접한 점의 업데이트에 영향을 미치므로 입력받은 원본 그대로의 map에서 각 점에 대한 update 값(isolatedFLag)을 구하고 모든 점을 동시에 업데이트해야 한다.

정리하면 각 점에 대한 isolatedFlag를 구하기 위한 BFS 한 사이클, map 업데이트, 빙산을 구하기 위한 BFS 한 사이클을 돌리면 된다.

추가적으로 빙산이 분리되는 최초의 시간을 구하기 위해 위 과정을 반복해야 하는데 매 과정이 시작될 때마다 map, vis, isolatedFlag를 초기화해주어야 한다.

마지막으로 빙산이 나누어지지 않는 edge case도 생각해야 하는데(이거 고려 안 했다가 엄청 틀렸다..) 마지막 if문이 그 조건이다. 마지막 if문 2개의 순서도 주의해야 한다.

✔ 정답 Code

#include <bits/stdc++.h>

using namespace std;

int mapp[300][300];
int isolatedFlag[300][300];
int vis[300][300];

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    int num, year = 0;
    while (1) { // year pass by...
        memset(vis, 0, sizeof(vis));
        memset(isolatedFlag, 0, sizeof(isolatedFlag));
        num = 0;

        // update isolatedFlag
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mapp[i][j] == 0 or vis[i][j]) continue;
                queue < pair < int, int > > Q;
                vis[i][j] = 1;
                Q.push({
                    i,
                    j
                });
                while (!Q.empty()) {
                    auto cur = Q.front();
                    Q.pop();
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cur.first + dx[dir];
                        int ny = cur.second + dy[dir];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        if (vis[nx][ny] == 0 && mapp[nx][ny] != 0) {
                            vis[nx][ny] = 1;
                            Q.push({
                                nx,
                                ny
                            });
                        } else if (mapp[nx][ny] == 0) { // sea
                            if (mapp[cur.first][cur.second] > 0) isolatedFlag[cur.first][cur.second]++;
                        }

                    }
                } // while

            } // j
        } // i

        // update map
        for (int k = 0; k < n; k++) {
            for (int p = 0; p < m; p++) {
                mapp[k][p] -= isolatedFlag[k][p];
                if (mapp[k][p] < 0) mapp[k][p] = 0;
            }
        }

        memset(vis, 0, sizeof(vis));
        // count island
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mapp[i][j] == 0 or vis[i][j]) continue;
                num++;
                queue < pair < int, int > > QQ;
                vis[i][j] = 1;
                QQ.push({
                    i,
                    j
                });
                while (!QQ.empty()) {
                    auto cur = QQ.front();
                    QQ.pop();
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cur.first + dx[dir];
                        int ny = cur.second + dy[dir];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        if (vis[nx][ny] == 0 && mapp[nx][ny] != 0) { // unvisited island
                            vis[nx][ny] = 1;
                            QQ.push({
                                nx,
                                ny
                            });
                        }
                    }
                } // while

            } // j
        } // i
        
        year++;
        if (num == 0) {
            cout << 0;
            return 0;
        }
        if (num != 1) break;

    } // while

    cout << year;

}

✔ Check Point

map 업데이트 과정에서 먼저 방문한 점이 업데이트되면 다른 점의 업데이트에 영향을 미치는 경우, 업데이트Flag 구하는 과정과 업데이트하는 과정을 분리해야 한다

특정한 값(MIN, MAX)을 구하기 위해 BFS 등을 반복할 때 매 과정 시작에 vis 등을 초기화해주어야 한다는 것 주의

edge case(빙산이 나누어지지 않는 경우 등)에 주의할 것