백준[2573] - 빙산

문제

백준 2573 문제 보기

접근 방법

빙산을 주변으로 4방향을 검사한 뒤 각 면이 몇개의 바다에 둘러 쌓여 있는지 모두 확인한다. 그리고 완전 탐색을 이용해 빙산이 분리됐는지 체크한다.

코드

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

using namespace std;

int r, c;
int map[301][301];
int visited[301][301];
int map_copied[301][301];
vector<pair<int, int>> ice;
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

void dfs(int rr, int cc) {
    for(int a = 0; a < 4; a ++) {
        int nextR = rr + dr[a];
        int nextC = cc + dc[a];
        if(nextC >= 0 && nextR >= 0 && nextC < c && nextR < r) {
            if(map[nextR][nextC] > 0 && visited[nextR][nextC] != 1) {
                visited[nextR][nextC] = 1;
                dfs(nextR, nextC);
            }
        }
    }
}

int main() {
    cin >> r >> c;

    for(int i = 0; i < r; i ++) {
        for(int j = 0; j < c; j ++) {
            cin >> map[i][j];

            if(map[i][j] > 0) {
                // 빙산의 좌표 저장
                ice.push_back({i, j});
            }
        }
    }

    // 년수 초기화
    int year = 0;

    while(1) {
        memset(map_copied, 0, sizeof(map_copied));
        memset(visited, 0, sizeof(visited));
        year ++;

        for(int i = 0; i < ice.size(); i ++) {
            int rr = ice[i].first;
            int cc = ice[i].second;
            int cnt = 0;

            // 빙산이 존재한다면
            if(map[rr][cc] > 0) {
                // 4방향으로 바다가 존재하는지 검사
                for(int a = 0; a < 4; a ++) {
                    int nextR = rr + dr[a];
                    int nextC = cc + dc[a];

                    if(nextC >= 0 && nextR >= 0 && nextC < c && nextR < r) {
                        if(map[nextR][nextC] == 0) {
                            cnt ++;
                        }
                    }
                }
            }
            // 1년후 빙산의 높이
            int num = map[rr][cc] - cnt;
            if(num > 0)
                map_copied[rr][cc] = num;
            else
                map_copied[rr][cc] = 0;
        }

        // 기존 맵에 감소한 빙산 높이를 저장
        memcpy(map, map_copied, sizeof(map_copied));

        int ans = 0;
        // 검사
        for(int i = 0; i < r; i ++) {
            for(int j = 0; j < c; j ++) {
                if(map[i][j] > 0 && visited[i][j] != 1) {
                    visited[i][j] = 1;
                    dfs(i, j);
                    ans ++;
                }
            }
        }

        if(ans > 1) {
            cout << year;
            return 0;
        } else if(ans == 0) {
            cout << 0;
            return 0;
        }
    }
}