2573 빙산

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

지구온난화로 인하여 북극의 빙산이 녹고 있다. 1년이 지날 때마다 빙산의 각 칸은 인접한 바다의 칸의 개수만큼 녹는다. 이 때 최초로 빙산이 2개로 나눠지는 시점을 구하는 문제이다. 매 시점마다 DFS로 섬의 개수를 세주고 2개 이상이면 루프를 탈출하고 답을 출력한다. 아직 빙산이 분리되지 않았다면 water 함수를 통해 빙산의 각 칸마다 인접한 바다의 개수를 구해서 저장해놓고 빙산의 상태를 갱신한다. 이 때 2개로 나눠지기 전에 모두 바다로 변한다면 0을 출력한다.

#include <cstdio>
#include <cstring>
 
int map[305][305],visit[305][305],tmap[305][305];
int n,m,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
 
int water(int x,int y)
{
    int cnt=0;
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(!map[nx][ny]) cnt++;
    }
    return cnt;
}
 
void dfs(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
        if(map[nx][ny] && !visit[nx][ny])
            visit[nx][ny]=true,dfs(nx,ny);
    }
}
 
void solve()
{
    int time=0;
    bool f=false;
    while(true)
    {
        // 현재 섬의 개수가 2개 이상이면 종료
        int cnt=0;
        for(int i=0;i<n;i++) for(int j=0;j<m;j++)
            if(map[i][j] && !visit[i][j])
                    visit[i][j]=true,cnt++,dfs(i,j);
        if(cnt>=2) { f=true; break; }
 
        for(int i=0;i<n;i++) for(int j=0;j<m;j++)
            if(map[i][j]) tmap[i][j]=water(i,j);
 
        for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(map[i][j])
            if((map[i][j]-=tmap[i][j])<0) map[i][j]=0;
 
        // 현재 모두 바다(0)인지 확인
        bool f2=false;
        for(int i=0;i<n;i++) for(int j=1;j<m;j++)
            if(map[i][j]) f2=true;
        if(!f2) break;
 
        memset(visit,0,sizeof(visit));
        time++;
    }
 
    printf("%d",f?time:0);
}
 
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        scanf("%d",&map[i][j]);
    solve();
    return 0;
}