[C++] 백준 2573:빙산

 

1. 문제

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

 

 

2. 문제 풀이

문제의 핵심은 다음과 같다.

• 빙산과 바다 데이터를 2차원 배열로 입력받는다.
• 바다에 많이 접한 빙산일 수록 높이가 더 빨리 줄어든다.
• 1년마다 빙산의 높이가 줄어든다.
• 덩어리가 2개 이상으로 분리되는 최초의 시간을 출력한다.

 

처음에는 BFS를 1번 돌면서 0에 맞닿아 있는 수만큼 값을 빼주었더니, 0이 되어버린 경우까지 포함되어서 BFS를 두 번 도는 방법을 택했다. 할 일은 다음과 같이 2가지로 나눌 수 있다.

1. 컴포넌트 개수 세기
2. 주변의 바다(0) 개수만큼 높이 낮추기

컴포넌트를 세는 BFS, 주변의 바다 개수만큼 빼주는 BFS를 구현해보자. 먼저 컴포넌트를 세는 건 일반 BFS처럼 방문처리하고 q에서 하나씩 읽어오면 된다. 주변의 바다 개수만큼 빼야 하는데, 먼저 주변 0의 개수를 세어준다. 그리고 기존 배열에서 주변 0의 개수를 빼준다. 이때, 뺀 값이 음수가 되면 안되기 때문에 value > 0인 경우에만 업데이트해주는 것이다. 또, 여기에서 바로 arr로 업데이트하지 않는 이유는 업데이트된 상태에서 주변의 0을 계산해버리면 계산 오류가 발생하기 때문에 tmp로 받아 bfs 한 번이 끝나고 나면 본 배열 arr에 업데이트한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring> 

using namespace std;

queue<pair<int, int> > q;
vector<vector<int> > arr;
int tmp[300][300] = {0,};
int visited[300][300] = {0,};

int n, m;
int ans = 0; // * 몇 년만에 두 덩이로 분리되는지

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

void bfs(int x, int y) {
    q.push(pair<int, int>(x, y));

    while (!q.empty()) {
        int cur_x = q.front().first;
        int cur_y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur_x + dx[i];
            int ny = cur_y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] != 0 && visited[nx][ny] == 0) {
                q.push(pair<int, int> (nx, ny));
                visited[nx][ny] = 1;
            }
        }
    }
}

void melt() {
    memset(tmp, 0, sizeof(tmp));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] != 0) {
                int cnt = 0;
                for (int k = 0; k < 4; k++) {   
                    int nx = i + dx[k];
                    int ny = j + dy[k];

                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] == 0) {
                        cnt++;
                    }
                }
                int value = arr[i][j] - cnt;
                if (value > 0) tmp[i][j] = value;
            }
        }
    }

    for (int i = 0; i<n; i++) {
        for (int j = 0; j<m; j++) {
            arr[i][j] = tmp[i][j];
        }
    }
}

int main() {
    cin >> n >> m;
    arr.resize(n, vector<int> (m));

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

    // * 몇 덩이인지 확인하고 두 덩이이면 ans 출력
    while (1) {
        memset(visited, 0, sizeof(visited));
        int component = 0; // * 몇 덩이

        for (int i = 0; i < n; i++) {
            for (int j =0; j<m; j++) {
                if (visited[i][j] == 0 && arr[i][j]!= 0) {
                    component++;
                    bfs(i, j);
                }
            }
        }

        if (component == 0) {
            cout << 0 << endl;
            break;
        }
        else if (component >= 2) {
            cout << ans << endl;
            break;
        }

        ans++;
        melt();
    }
}