백준 2573 빙산 (C++)

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

 

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

using namespace std;

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

vector<vector<int>> arr;
bool visit[301][301];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    int ans = 0;
    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];
        }
    }


    while (true) {

        //빙하 녹이기
        ans++;                  //햇수
        vector<vector<int>> temp(n, vector<int>(m, 0));
        queue<pair<int, int>> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                int mCnt = 0;

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



                        if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                            if (arr[ny][nx] == 0) {
                                mCnt++;
                            }
                        }

                    }

                    temp[i][j] = arr[i][j] - mCnt >= 0 ? arr[i][j] - mCnt : 0;
                }
            }
        }

        arr = temp;

        //덩어리 수 확인
        int cnt = 0;
        bool isAllMelt = true;
        fill_n(&visit[0][0], 301 * 301, false);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] != 0 && !visit[i][j]) {
                    isAllMelt = false;
                    q.push(make_pair(i, j));
                    visit[i][j] = true;
                    cnt++;



                    while (!q.empty()) {
                        pair<int, int> cur = q.front();
                        q.pop();

                        for (int k = 0; k < 4; k++) {
                            int ny = cur.first + dy[k];
                            int nx = cur.second + dx[k];

                            if (ny >= 0 && ny < n && nx >= 0 && nx < m) {

                                if (!visit[ny][nx] && arr[ny][nx] != 0) {
                                    q.push(make_pair(ny, nx));
                                    visit[ny][nx] = true;
                                }


                            }

                        }

                    }
                }
            }
        }

        if (isAllMelt) {
            cout << 0;
            return 0;
        }

        if (cnt >= 2) {
            break;

        }

    }

    cout << ans;

    return 0;
}

1. 문제

n*m의 빙산의 크기가 주어진다. 0은 바다를 뜻한다. 빙산은 매 해 상하좌우의 바다의 수 만큼 녹는다. 어떤 빙산의 상하좌우에 빙산이 존재할 경우 해당 빙산들은 한 덩어리로 간주한다. 한 덩어리의 빙산이 주어졌을 때 해당 빙산이 두 덩어리로 분리되는 최초의 시간(년)을 구하라. 단, 모든 빙산이 녹아 없어질 때 까지 두 덩어리 이상으로 분리되지 않을 경우 0을 출력한다.

2. 풀이

이 문제의 과정은 다음과 같다.

1. 매 해 빙산을 녹이기
2. 빙산의 덩어리 수를 확인하기

 //빙하 녹이기
        ans++;                  //햇수
        vector<vector<int>> temp(n, vector<int>(m, 0));
        queue<pair<int, int>> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                int mCnt = 0;

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



                        if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                            if (arr[ny][nx] == 0) {
                                mCnt++;
                            }
                        }

                    }

                    temp[i][j] = arr[i][j] - mCnt >= 0 ? arr[i][j] - mCnt : 0;
                }
            }
        }

        arr = temp;

빙산을 녹인다. 먼저 녹은 빙산이 다음 빙산에 영향을 끼치지 않도록 temp 배열을 사용한다. 배열을 돌면서 빙산이 존재할 경우 상하좌우를 탐색하여 0의 개수만큼 녹인다. 이 과정이 끝나면 원 배열 arr에 연산 결과를 옮긴다.

//덩어리 수 확인
        int cnt = 0;
        bool isAllMelt = true;
        fill_n(&visit[0][0], 301 * 301, false);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] != 0 && !visit[i][j]) {
                    isAllMelt = false;
                    q.push(make_pair(i, j));
                    visit[i][j] = true;
                    cnt++;



                    while (!q.empty()) {
                        pair<int, int> cur = q.front();
                        q.pop();

                        for (int k = 0; k < 4; k++) {
                            int ny = cur.first + dy[k];
                            int nx = cur.second + dx[k];

                            if (ny >= 0 && ny < n && nx >= 0 && nx < m) {

                                if (!visit[ny][nx] && arr[ny][nx] != 0) {
                                    q.push(make_pair(ny, nx));
                                    visit[ny][nx] = true;
                                }


                            }

                        }

                    }
                }
            }

빙산의 덩어리 개수는 BFS로 확인할 수 있다. 배열을 돌며 빙산을 발견한 경우, 해당 빙산 덩어리를 세어 주고,  해당 위치에서 시작하여 상하좌우에 있는 빙산으로 BFS를 돌린다. 이렇게 하면 같은 덩어리의 빙산은 자연스레 방문하지 않을 수 있다. isAllMelt를 선언하여 모든 빙산이 녹지는 않았는지 확인한다.

        if (isAllMelt) {
            cout << 0;
            return 0;
        }

        if (cnt >= 2) {
            break;

        }

    }

    cout << ans;

    return 0;

모든 빙산이 녹았다면 0을 출력하고 프로그램을 종료한다. 빙산 덩어리가 2개 이상인 경우 반복문을 종료, 해당 햇수를 출력한다.