빙산 (feat. 백준, 2573번)

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

2573번: 빙산

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, dx[4], dy[4], arr[301][301], tmp[301][301];
bool visit[301][301];
void melt(){
    for(register int x = 1, y; x <= N; ++x)
        for(y = 1; y <= M; ++y){
            tmp[x][y] = arr[x][y];
            if(tmp[x][y] > 0){
                for(register int d = 0, nx, ny; d < 4; ++d){
                    nx = x + dx[d], ny = y + dy[d];
                    if(1 <= nx && nx <= N && 1 <= ny && ny <= M && arr[nx][ny] == 0)
                        --tmp[x][y];
                }
                if(tmp[x][y] < 0)
                    tmp[x][y] = 0;
            }
        }
    for(register int x = 1, y; x <= N; ++x)
        for(y = 1; y <= M; ++y)
            arr[x][y] = tmp[x][y];
}
bool bfs(){
    memset(visit, false, sizeof(visit));
    register int tmp = 0;
    queue<pair<int, int>> q;
    for(register int n = 1, m; n <= N; ++n)
        for(m = 1; m <= M; ++m)
            if(!visit[n][m] && arr[n][m] > 0){
                if(++tmp > 1)
                    return true;
                q.push(make_pair(n, m));
                visit[n][m] = true;
                while(!q.empty()){
                    auto p = q.front(); q.pop();
                    register int x = p.first, y = p.second;
                    for(register int d = 0, nx, ny; d < 4; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(1 <= nx && nx <= N && 1 <= ny && ny <= M && !visit[nx][ny] && arr[nx][ny] > 0)
                            visit[nx][ny] = true, q.push(make_pair(nx, ny));
                    }
                }
            }
    return false;
}
bool check(){
    for(register int n = 1, m; n <= N; ++n)
        for(m = 1; m <= M; ++m)
            if(arr[n][m] > 0)
                return true;
    return false;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    cin >> N >> M;
    for(register int n = 1, m; n <= N; ++n)
        for(m = 1; m <= M; ++m)
            cin >> arr[n][m];
    register int ans = 0;
    while(++ans){
        melt();
        if(bfs())
            break;
        else if(!check()){        // 빙산이 한덩어리고 다 녹은 경우, 정답은 0
            ans = 0;
            break;
        }
    }
    cout << ans;
    return 0;
}
// *&)*@*

 

 

1. 한 덩어리의 빙산이 입력값으로 주어지므로 최초에는 1년도를 증가시키고 빙산을 녹입니다.
2. 녹은 빙산 기준으로 2덩어리 빙산이 된다면 bfs를 종료시키고 증가된 총 연도를 출력합니다.
3. 2번에서 2덩어리가 되지 못한다면 전체 빙산을 조사하며 모두 녹은 경우인지를 확인합니다. 만약 모두 녹은 상태라면 0을 출력합니다.