[C++/백준] 2573번: 빙산

문제 링크

2573번: 빙산

 

풀이

DFS 문제

1. while 반복문으로 한 해의 빙산 덩어리 개수를 계산한다.
   1. 매 년마다 DFS로 덩어리의 개수를 세야하기 때문에 visit은 지역변수로 넣어줬다.
   2. cnt는 덩어리의 개수이고, flag는 빙산이 다 녹았는지 체크하기 위한 bool 변수이다.
   3. 만약 방문하지 않은 빙산이 있다면 덩어리 개수를 +1해주고, DFS를 실행한다. 빙산이 있다는 뜻이므로 flag도 false해준다.
2. DFS 함수는 덩어리 하나를 체크하기 위한 함수임과 동시에 일 년이 지나고 빙산을 만들어준다.
   1. 덩어리 개수 체크를 위해 visit은 받아와주었고, 방문처리를 한다.
   2. zeroCnt에는 해당 빙산이 바다와 맞닿아있는 면적(상하좌우)이 구해질 것이다.
   3. 해당 빙산의 상하좌우를 체크해 범위 밖이거나 방문했다면 continue,
   4. 바다라면 zeroCnt++해준 뒤, continue 해준다.
   5. 새로운 빙산에서 다시 DFS를 재귀호출한다.
   6. arr[y][x] 빙산에서 상하좌우 체크가 다 끝났다면 더 이상 방문해줄 일이 없기 때문에 미리 일년 뒤의 빙산 상태로 만들어준다.
   7. arr[y][x]에 미리 구해뒀던 바다와 맞닿은 면적 zeroCnt를 빼주고, 0보다 작아진다면 0으로 만들어준다.
3. 그렇게 구해진 덩어리의 개수 cnt가 2개 이상이라면 해당 년도까지의 시간 time을 출력해주고 return한다.
4. 빙산이 다 녹아버렸다면 (flag==true) 0을 출력해준다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };

void DFS(vector<vector<int>> &arr, vector<vector<int>> &visit, int y, int x)
{
    visit[y][x] = 1;
    int zeroCnt = 0;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || ny >= arr.size() || nx < 0 || nx >= arr[0].size()) continue;
        if (visit[ny][nx]) continue;
        if (arr[ny][nx] == 0)
        {
            zeroCnt++;
            continue;
        }
        DFS(arr, visit, ny, nx);
    }
    arr[y][x] -= zeroCnt;
    if (arr[y][x] < 0) arr[y][x] = 0;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr(n, vector<int>(m));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
        }
    }

    int time = 0;
    while (true)
    {
        vector<vector<int>> visit(n, vector<int>(m));

        int cnt = 0; // 덩어리 개수
        bool flag = true; // 다 녹았는지 flag

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (arr[i][j] > 0 && visit[i][j] == 0)
                {
                    cnt++;
                    flag = false;
                    DFS(arr, visit, i, j);
                }
            }
        }
        if (cnt >= 2) // 두 덩어리 이상 분리됐다면
        {
            cout << time;
            break;
        }
        else if (flag) // 다 녹았다면
        {
            cout << "0";
            break;
        }

        time++;
    }
}