2573번

2573번 - 빙산

연결요소의 갯수를 구하는 문제이기 때문에 dfs 를 이용해서 문제를 풀었다.

그리고 빙산이 계속 녹아야 하기 때문에, 맵을 계속 갱신해주는 remake 함수를 만들었다.

빙산의 연결 요소가 2개 이상이 되면 바로 출력해준다.

단 빙산이 하나도 없는 경우에는 0을 출력해준다.

<정답 코드>

#include<iostream>
#include<vector>
 
using namespace std;
 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int n, m;
vector<vector<int>> remake(vector<vector<int>> map)
{
    vector<vector<int>> ret = map;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int num = 0;
            for (int k = 0; k < 4; k++)
            {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny]==0)
                {
                    num++;
                }
            }
            if (ret[i][j] != 0)
            {
                ret[i][j] -= num;
                if (ret[i][j] < 0)
                {
                    ret[i][j] = 0;
                }
            }
            
        }
    }
 
    return ret;
}
 
void dfs(int x, int y, vector<vector<bool>> &check, vector<vector<int>> &map)
{
    check[x][y] = true;
 
    for (int k = 0; k < 4; k++)
    {
        int nx = x + dx[k];
        int ny = y + dy[k];
 
        if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] != 0 && !check[nx][ny])
        {
            dfs(nx, ny, check, map);
        }
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &m);
    vector<vector<int>> map(n, vector<int>(m));
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
 
    int year = -1;
    while (true)
    {
        int bingsan = 0;
        year++;
        vector<vector<bool>> check(n, vector<bool>(m,false));
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (!check[i][j] && map[i][j]!=0)
                {
                    bingsan++;
                    if (bingsan >= 2)
                    {
                        printf("%d\n", year);
                        return 0;
                    }
                    dfs(i, j,check,map);
                }
            }
        }
 
        if (bingsan == 0)
        {
 
            printf("0\n");
            break;
        }
 
        map=remake(map);
    }
 
    return 0;
}