2573 빙산

문제 링크

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

풀이

빙산의 정보를 2차원 배열 arr에 저장한다. 녹은 후의 상태로 arr를 업데이트 해주는 melt 함수와 한 덩어리의 빙산을 탐색하며 visit을 true로 업데이트 시켜주는 dfs 함수가 있다. melt에서는 arr의 복사본 tmp를 생성하여 tmp의 빙산의 각 칸에서 상하좌우의 0개수를 세어준 후 arr의 빙산의 각 칸에서 주변의 0의 개수만큼을 빼준다. 바로 업데이트 하지 않고 복사본을 생성하는 이유는 arr가 업데이트 되면서 주변의 0의 개수가 바뀔 수 있기 때문이다. 이때 빙산의 칸의 값이 0보다 작아지면 0으로 바꾸어준다. melt 함수는 리턴값으로 업데이트 시켜준 빙산의 칸의 개수를 반환한다. 만약 반환값이 0이라면(즉 빙산이 쪼개지기 전에 전부 녹아버려 더 녹을 빙산이 없다면) 0을 출력하고 종료한다. main함수에서는 반복문을 돌면서 만약 melt가 실행된 후 녹지 않은 칸이 있다면 dfs를 실행시켜 인접한 칸을 확인하며 visit을 false로 업데이트 시킨다. dfs를 한번 실행시킨 후 탐색한 칸 중 visit이 false면서 녹지 않은 빙산이 있다면 빙산이 2개 이상 있다는 것이므로(즉 빙산이 쪼개졌다는 뜻이므로) 현재까지 흐른 시간을 출력하고 종료한다.

C++ 코드

#include <iostream>
#include <string.h> // use memset

using namespace std;

int N, M;
int arr[300][300];
bool visit[300][300];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void dfs(int x, int y){
    visit[x][y] = true;
    
    for(int i=0; i<4; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(0<=nx && nx<N && 0<=ny && ny<M && !visit[nx][ny] && arr[nx][ny]>0)
            dfs(nx, ny);
    }
    
}

// 빙산을 녹은 후의 값으로 업데이트하는 melt 함수
int melt(){
    int tmp[300][300];
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            tmp[i][j] = arr[i][j];
        }
    }
    int left = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            int m = 0;
            if(tmp[i][j] != 0){
                left++;
                for(int n=0; n<4; n++){
                    int nx = i+dx[n];
                    int ny = j+dy[n];
                    if(tmp[nx][ny] == 0) m++;
                }
                arr[i][j] -= m;
            	if(arr[i][j] < 0) arr[i][j] = 0;
            }
        }
    }
    
    // 업데이트 시킨 빙산의 칸의 개수(0이라면 이미 전부 녹아 업데이트 시킬 칸이 없다는 뜻)
    return left;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>N>>M;
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin>>arr[i][j];
        }
    }
    
    int time = 0;
    while(true){
    	// visit false로 초기화
    	memset(visit, false, sizeof(visit));
        // 빙산의 개수
    	int iceberg = 0;
    	for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(!visit[i][j] && arr[i][j] > 0){
                    iceberg++;
                    if(iceberg > 1){cout<<time<<endl; return 0;}
                    dfs(i, j);
                }
            }
        }
        int n = melt();
        if(n == 0) {cout<<0<<endl; return 0;}
        time++;
    }
    
    return 0;
}