[C++] 백준/Gold/2573. 빙산

문제: 빙산 (백준 2573번)

간만의 구현 문제이다. 구현 문제는 말 그대로 구현하는 데 시간이 많이 걸리기 때문에 사용하는 알고리즘 자체는 크게 어렵지 않은 경우가 많다. 이번 문제도 그런 케이스이며, 전체적인 로직은 다음과 같다.

문제 의도

• 배열에 1 이상의 수가 남아있는 동안 반복
  • time을 증가시키고
  • 2차원 배열을 돌며 상하좌우의 0의 개수와 해당 좌표를 저장
  • 저장해둔 0의 개수만큼 해당 좌표의 값을 감소 (0 미만이 되지 않도록)
  • 2차원 배열을 돌며 BFS로 그룹 개수 체크
  • 그룹 개수가 2개 이상이면 반복문을 정지
• 배열의 1 이상의 수가 있으면 time을 출력
• 아니면 0을 출력

알고리즘 개요

1. 시간(time) 증가
   • 매번 반복할 때마다 시간을 증가시킨다.
2. 녹을 빙산 계산
   
   • 각 좌표에서 상하좌우로 바다가 몇 칸 있는지 계산하여, 그 수만큼 빙산을 녹인다.
   • 이때 빙산의 크기는 0 미만이 될 수 없으므로 clamp를 사용하여 값을 0과 10 사이로 제한한다.
3. 빙산 그룹 개수 체크
   • BFS를 사용하여 얼음 덩어리(빙산)가 몇 개로 분리되는지 확인한다.
   • 만약 2개 이상의 덩어리가 되면 더 이상 진행할 수 없고 반복문을 종료한다.
4. 사이클 종료 여부 확인
   • 모든 얼음이 녹았으면 0을 출력하고, 여전히 얼음이 남아있으면 time을 출력한다.

코드 구현

#include <bits/stdc++.h>
using namespace std;

bool Check(vector<vector<int>> &v) {
    for (auto& i : v) {
        for (auto& j : i) {
            if (j > 0) return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<int>> v(n, vector<int>(m));
    
    // 입력 받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
        }
    }

    int time = 0;
    int offset[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
    vector<vector<bool>> ocean(n, vector<bool>(m));
    ocean[0][0] = true;

    while (Check(v)) {
        time++;

        // 녹을 빙산 계산
        vector<tuple<int, int, int>> ocean;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!v[i][j]) continue;
                int sum = 0;
                for (int k = 0; k < 4; k++) {
                    int xx = j + offset[k][0];
                    int yy = i + offset[k][1];
                    if (xx < 0 || xx >= m || yy < 0 || yy >= n || v[yy][xx]) continue;
                    sum++;
                }
                ocean.push_back({ i, j, sum });
            }
        }

        // 계산된 결과값 적용
        for (auto& i : ocean) {
            int x, y, cost; tie(y, x, cost) = i;
            v[y][x] = clamp(v[y][x] - cost, 0, 10);
        }

        // 그룹 개수 체크
        vector<vector<bool>> visited(n, vector<bool>(m));
        int iceberg = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!v[i][j] || visited[i][j]) continue;
                iceberg++;
                queue<pair<int, int>> q;
                q.push({ i, j });
                visited[i][j] = true;
                while (!q.empty()) {
                    int x, y; tie(y, x) = q.front();
                    q.pop();
                    for (int k = 0; k < 4; k++) {
                        int xx = x + offset[k][0];
                        int yy = y + offset[k][1];
                        if (xx < 0 || xx >= m || yy < 0 || yy >= n) continue;
                        if (v[yy][xx] && !visited[yy][xx]) {
                            visited[yy][xx] = true;
                            q.push({ yy, xx });
                        }
                    }
                }
            }
        }

        // 2개 이상의 그룹이 생기면 종료
        if (iceberg > 1) break;
    }

    // 모든 얼음이 녹았으면 0, 아니면 time 출력
    if (Check(v)) cout << time;
    else cout << 0;
}

주요 설명

1. Check 함수:
   • 배열을 돌면서 얼음이 하나라도 남아있는지 확인한다. 남아있다면 true, 아니면 false를 반환한다.
2. 녹을 빙산 계산:
   • 각 빙산에서 상하좌우로 바다가 몇 칸 있는지 계산하고, 그 수만큼 빙산을 녹인다. 이때 빙산의 크기는 0 이상이어야 하므로 clamp 함수를 사용하여 값을 0과 10 사이로 제한한다.
3. 그룹 개수 체크:
   • BFS를 사용하여 얼음 덩어리(빙산)가 몇 개로 분리되는지 확인한다.
   • iceberg 변수로 그룹의 개수를 세고, 2개 이상의 그룹이 생기면 반복문을 종료한다.
4. 최종 출력:
   • 모든 얼음이 녹았다면 0을 출력하고, 그렇지 않으면 time을 출력한다.