백준 문제 2573번 빙산 문제풀이 c++

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

2573번: 빙산

 

문제해석

 

dfs 또는 bfs로 이 문제를 풀 수있다.

 

난 dfs로 구현하였는데 bfs로 구현해도 상관없다 먼저 종료 조건 부터 생각해보자.

 

모든 빙산이 녹거나 또는 빙산섬이 두개로 분리 될때까지 탐색을 계속 돌려주면된다.

 

dfs는 물이 아닐때 즉 빙산일때 돌려 주면 되고 dfs를 한번 돌릴때마다 섬의 개수를 하나 세주면 된다.

 

섬이 2개가 된 순간 즉시 시간을 출력하고 종료를 하면된다.

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool all_melt();
void dfs(int cy,int cx);
bool inside(int ny,int nx);
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
int a[300][300];
int cnt[300][300];
bool visited[300][300];
int n,m;
int t=0;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>a[i][j];
        }
    }
    while(!all_melt())
    {
        int island=0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(a[i][j]!=0)
                {
                    if(visited[i][j]==0)
                    {
                        dfs(i,j);
                        island++;
                        if(island>1)
                        {
                            cout<<t;
                            return 0;
                        }
                    }
                }
            }
        }
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                for(int k=0; k<4; k++)
                {
                    int ny=i+dy[k];
                    int nx=j+dx[k];
                    if(inside(ny,nx)&&a[ny][nx]==0)
                    {
                        cnt[i][j]++;
                    }
                }
            }
        }
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                a[i][j]=max(0,a[i][j]-cnt[i][j]);
                cnt[i][j]=0;
                visited[i][j]=0;
            }
        }
        t++;
    }
    cout<<0;
}
bool all_melt(){
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(a[i][j]!=0)
            {
                return false;
            }
        }
    }
    return true;
}
void dfs(int cy,int cx){
    visited[cy][cx]=1;
    for(int i=0; i<4; i++)
    {
        int ny=cy+dy[i];
        int nx=cx+dx[i];
        if(a[ny][nx]!=0&&visited[ny][nx]==0)
        {
            dfs(ny,nx);
        }
    }
}
bool inside(int ny,int nx){
    if(0<=ny&&ny<n&&0<=nx&&nx<m)
    {
        return true;
    }
    else
    {
        return false;
    }
}