[99클럽/코딩테스트 챌린지/C++] 빙산 문제 풀이

지구 온난화로 빙산이 녹으면서, 빙산이 여러 덩어리로 분리되는 최초의 시간을 구하는 문제입니다. 매년 빙산은 바닷물과 접한 부분만큼 높이가 줄어듭니다. 주어진 2차원 배열에서 각 빙산의 위치와 높이를 바탕으로 매년 빙산이 녹는 과정을 시뮬레이션하며, 빙산이 분리되는 최초의 시간을 출력합니다. 만약 모든 빙산이 녹을 때까지 분리되지 않는다면 0을 출력합니다.

문제 링크 :

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

접근법

1, 빙산 높이 감소 시뮬레이션:

• 매년 동서남북 방향으로 바다(0)와 접촉하는 부분만큼 빙산의 높이를 줄입니다. 이를 afterYear() 함수로 구현하여, 각 칸마다 인접한 바다의 개수를 세고 빙산 높이를 줄입니다.

2, 빙산 덩어리 개수 확인:

• 매년 빙산의 덩어리 수를 BFS를 통해 확인합니다. BFS 탐색을 통해 연결된 빙산 덩어리를 찾아냅니다. 하나의 덩어리라면 분리가 일어나지 않은 상태이며, 두 개 이상으로 나뉘면 분리된 것으로 판단합니다.

3, 종료 조건:

• 만약 특정 해에 빙산이 두 개 이상으로 나뉘면 그 해를 출력하고 종료합니다.
• 모든 빙산이 다 녹아 0이 되었지만 두 덩어리 이상으로 분리되지 않았다면 0을 출력합니다.

코드 설명

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int Y, X;
vector<vector<int>> maps;
vector<vector<int>> visited;

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

bool afterYear()
{
    vector<vector<int>> toRemove =
        vector<vector<int>>(Y, vector<int>(X, 0));
    for (int y = 0; y < Y; y++)
    {
        for (int x = 0; x < X; x++)
        {
            if (maps[y][x] <= 0) continue;
            for(int i = 0; i < 4; i++)
            {
                int ny = dy[i] + y;
                int nx = dx[i] + x;

                if(ny < 0 || ny > Y || nx < 0 || nx > X) continue;

            	if(maps[ny][nx] <= 0)
                {
                    toRemove[y][x]++;
                }
            }
        }
    }
    int total = 0;
    for (int y = 0; y < Y; y++)
    {
        for (int x = 0; x < X; x++)
        {
            if (maps[y][x] <= 0) continue;
            maps[y][x] -= toRemove[y][x];
            if (maps[y][x] <= 0) maps[y][x] = 0;
            total += maps[y][x];
        }
    }
    return total > 0;
}


int Found(int y , int x)
{
    queue<pair<int, int>> q;
    q.push({ y,x });
    visited[y][x] = 1;

    while (!q.empty())
    {
        pair<int, int> current = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int ny = dy[i] + current.first;
            int nx = dx[i] + current.second;

            if (ny < 0 || ny > Y || nx < 0 || nx > X) continue;
            if (maps[ny][nx] <= 0) continue;
            if (visited[ny][nx]) continue;
            visited[ny][nx] = 1;
            q.push({ ny,nx });
        }

    }
    return 1;
}

int main() {

    std::cin >> Y >> X;
    maps = vector<vector<int>>(Y, vector<int>(X, 0));
   
    for(int y = 0; y < Y; y++)
    {
	    for(int x = 0; x < X; x++)
	    {
            std::cin >> maps[y][x];
	    }
    }
    int count = 0;
    int years = 0;
    while (count < 2)
    {
        count = 0;
        visited = vector<vector<int>>(Y, vector<int>(X, 0));
        for (int y = 0; y < Y; y++)
        {
            for (int x = 0; x < X; x++)
            {
                if(maps[y][x] > 0 && !visited[y][x])
                {
                    count += Found(y, x);
                }
            }
        }
        if(count >= 2)
        {
	        break;
        }

        if(!afterYear())
        {
            std::cout << 0 << '\n';
            return 0;
        }
        years += 1;
    }
    std::cout << years << '\n';

    return 0;
}

배운 점

1, BFS/DFS로 연결된 덩어리 찾기

BFS/DFS를 통해 연결된 영역을 탐색하여 분리된 덩어리를 찾는 방법을 확실히 이해할 수 있었습니다. 연결된 영역의 개수를 세는 방식이 분리 여부를 확인하는 데 매우 유용합니다.

 

2, 매년 변화하는 값의 시뮬레이션

해마다 달라지는 빙산의 상태를 시뮬레이션할 때, afterYear() 함수를 통해 각 칸의 상태를 일괄적으로 업데이트하고 매년 변화를 반영하는 방법을 배웠습니다.

결론

이 문제를 통해 BFS/DFS를 활용한 연결된 덩어리 탐색과 시뮬레이션을 통한 상태 변화 처리를 체계적으로 배울 수 있었습니다. 매년 빙산의 높이를 감소시키며 분리되는 최초의 시점을 찾는 과정을 통해, 조건에 따라 변하는 상태를 어떻게 관리하고 탐색하는지에 대한 경험을 쌓을 수 있었습니다.