BOJ 2573: 빙산

백윤재·2021년 9월 13일
0

BOJ

목록 보기
9/28
post-thumbnail

✔ 문제 링크


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(빙산이 나누어지지 않는 경우 등)에 주의할 것

✔ Comment

BFS를 응용하면 이렇게 낼 수도 있구나라는 생각이 들었다. 풀면서 얻어 가는 것이 많았다.

귀찮아서 문제만 풀고 포스팅을 미루고 있었는데 오늘부터 다시 하나씩 정리 시작... 리팩토링은 다음에 하는 걸로

profile
SKKU 18.5

0개의 댓글

관련 채용 정보