백준 2573 빙산 (C++)

2573번: 빙산

bfs를 이용한 문제이다. 과정은 아래와 같다.

1. 빙산이 모두 녹았는지 확인한다.
2. 빙산이 두덩이 이상으로 분리되었는지 확인한다.
3. 빙산을 녹인다.

반복문을 이용해 위의 과정을 반복해주었다. 빙산이 모두 녹았는지는 백터를 이용해 확인해주었다. 처음 입력값을 받을 때 0이 아닌 곳의 위치를 백터에 저장해주고 백터의 크기가 0이 된 경우를 빙산이 모두 녹았다고 판단하였다. 두덩이 이상으로 분리된지 확인하는 것은 bfs를 이용하였다. 벡터를 차레로 접근하면서 해당 위치와 인접한 빙산을 모두 구하고 이를 카운트하며 카운트가 2 이상이 된 경우를 두덩이 이상으로 분리되었다고 판단했다. 빙산을 녹이는 부분이 중요한데, 녹이는 과정에서 0이된 빙산을 기존에 있던 0과 분리하여 판단하기 위해 check를 하여 녹이는 과정에서의 오류를 잡아주었다. 이를 반복하여 두덩이 이상이 될 경우 걸린 시간을 출력해주고, 다 녹은 경우 0을 출력해주었다.
생각보다 오래 걸린 문제였다. 앞서 말한 빙산을 녹이는 알고리즘 부분에서 녹이는 과정에 0이된 경우를 기존 0과 같다고 판단해 잘못된 결과를 내어 실패가 계속해서 났었고, 이를 찾는 과정이 오래걸렸다. check를 꼭 사용하도록 하자.

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

using namespace std;

int N, M, res = 0;
int A[300][300];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
queue<pair<int, int>> q;
vector<pair<int, int>> v;
bool check[300][300];

void bfs() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            check[i][j] = false;
        }
    }

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        int count = 0;

        check[y][x] = true;

        q.pop();

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

            if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
            if (check[ny][nx]) continue;

            if (A[ny][nx] == 0) count++;
        }

        A[y][x] -= count;
        if (A[y][x] < 0) {
            A[y][x] = 0;
        }
    }

    for (int i = 0; i < v.size(); i++) {
        int y = v[i].first;
        int x = v[i].second;

        if (A[y][x] == 0) {
            v.erase(v.begin() + i);
            i--;
        }
    }
}

void check_bfs(int a, int b) {
    queue<pair<int, int>> tmp;

    tmp.push({ a,b });
    check[a][b] = true;

    while (!tmp.empty()) {
        int y = tmp.front().first;
        int x = tmp.front().second;
        int count = 0;

        tmp.pop();

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

            if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
            if (A[ny][nx] == 0) continue;
            if (check[ny][nx]) continue;

            tmp.push({ ny,nx });
            check[ny][nx] = true;
        }
    }
}

void solution() {
    while(1){
        if (v.size() == 0) break;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                check[i][j] = false;
            }
        }

        int count = 0;
        for (int i = 0; i < v.size(); i++) {
            int y = v[i].first;
            int x = v[i].second;

            if (check[y][x]) continue;

            check_bfs(y, x);

            count++;
        }

        if (count >= 2) break;

        for (int i = 0; i < v.size(); i++) {
            q.push({ v[i].first, v[i].second });
        }

        bfs();
        res++;
    }

    if (v.size() == 0) {
        cout << 0 << "\n";
    }
    else {
        cout << res << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> A[i][j];

            if (A[i][j] != 0) {
                v.push_back({ i,j });
            }
        }
    }

    solution();

    return 0;
}