[백준 2573] 빙산, C++

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

2573번: 빙산

 본 문제는 2006 한국정보올림피아드 초등부 2번 문제다. 지구 온난화로 인하여 북극의 빙산이 녹는다. 바닷물은 0, 빙산은 10이하의 자연수다. 빙산은 일년에 동서남북에 있는 바닷물의 개수만큼 줄어든다. 빙산이 두 덩어리 이상으로 분리되는 최초의 년을 출력하라. 이때, 빙산이 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 0을 출력하라.

문제 해결 과정

1. 빙산을 바닷물의 접촉 개수 만큼 줄인다.
   
   • 이때, tmp 배열에 빙산마다 녹는 정도를 따로 저장하여 계산해야 한다.
   • 왜냐하면, 인접해있는 빙산이 먼저 녹을 경우 2년에 다 녹아야 되는 빙산이 1년에 다 녹을 수도 있다.
2. 빙산이 두 덩어리로 분리확인
3. 다 녹을 때까지 분리가 안되면 0 출력

#include <cstdio>
#include <queue>
#include <cstring>
 
using namespace std;
 
int map[301][301];
int tmp[301][301];
bool chk[301][301];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    queue<pair<int, int>> q;
    int result = 0;
    while (true) {
        result += 1;
        memset(chk, false, sizeof(chk));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                tmp[i][j] = map[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) continue;
                int cnt = 0;
                for (int k = 0; k < 4; k++) {
                    int ni = i + dx[k];
                    int nj = j + dy[k];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
                        if (map[ni][nj] == 0) cnt += 1;
                    }
                }
                tmp[i][j] -= cnt;
                if (tmp[i][j] < 0) tmp[i][j] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = tmp[i][j];
            }
        }
        int ans = 0;
        for (int i = 0 ; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) continue;
                if (!chk[i][j]) {
                    chk[i][j] = true;
                    ans += 1;
                    q.push(make_pair(i, j));
                    while (!q.empty()) {
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();
                        for (int k = 0; k < 4; k++) {
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                                if (!chk[nx][ny] && map[nx][ny] != 0) {
                                    chk[nx][ny] = true;
                                    q.push(make_pair(nx, ny));
                                }
                            }
                        }
                    }
                }
            }
        }
        if (ans >= 2) {
            printf("%d\n", result);
            return 0;
        }
        else if (ans == 0) {
            printf("0\n");
            return 0;
        }
    }
}