[Algorithm/C++17] 백준 2573 빙산

문제

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

2573번: 빙산

풀이 방법

그래프 탐색을 활용한 구현 문제다. 주의해야 할 것은 시작부터 덩어리가 이미 분리되어 있는 케이스가 있기 때문에 녹이기 전에 먼저 덩어리 개수를 확인해줘야 한다. 따라서 현재 빙산의 높이 정보를 토대로 빙산의 덩어리가 두 덩어리 이상이면 현재 시간을 출력하고, 그렇지 않다면 문제의 설명대로 빙산을 녹이고 시간을 증가시키면 된다.

 

빙산의 덩어리 개수를 세는 알고리즘은 BFS나 DFS 모두 사용할 수 있다. (0, 0)부터 (N, M)까지 반복문을 돌면서 높이가 1이상인 빙산이 있다면 탐색을 시작해 이어진 모든 빙산을 방문했다고 체크하고 빙산 덩어리 개수인 count를 1 증가시킨다. 이해가 잘 되지 않는다면 이를 다루는 문제인 11724번 연결 요소의 개수 를 먼저 풀어보는 것이 좋다.

 

빙산을 녹이는 건 각자 구현하기 나름이지만 이 글에서는 그래프 탐색으로 구현했다. 다르게 구현해도 상하좌우 바닷물의 개수를 구하고 한 번에 모든 빙산의 높이를 감소시키면 별 다른 오류는 없을 것이다.

코드

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};
int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    vector<vector<int>> v(N, vector<int>(M, 0));
    queue<pair<int, int>> q;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            int t;
            scanf("%d", &t);
            v[i][j] = t;
            if(t > 0) q.push({i,j});
        }
    }
    int answer = 0;
    bool separated = false;
    while(!q.empty())
    {
    	// 빙산 덩어리가 두 덩어리 이상이면 루프문 탈출
    	int count = 0;
        queue<pair<int, int>> search_queue;
        vector<vector<bool>> visited(N, vector<bool>(M, false));
        for(int j=0; j<N; j++)
        {
            for(int k=0; k<M; k++)
            {
                if(v[j][k] == 0 || visited[j][k]) continue;
                search_queue.push({j,k});
                visited[j][k] = true;
                while(!search_queue.empty())
                {
                    auto p = search_queue.front();
                    search_queue.pop();
                    int y = p.first;
                    int x = p.second;
                    for(int j=0; j<4; j++)
                    {
                        int ny = y + dy[j];
                        int nx = x + dx[j];
                        if(0 > ny || ny > N | 0 > nx || nx > M) continue;
                        if(v[ny][nx] != 0 && !visited[ny][nx])
                        {
                            visited[ny][nx] = true;
                            search_queue.push({ny,nx});
                        }
                    }
                }
                count++;
            }
        }
        if(count >= 2)
        {
            separated = true;
            break;
        }
    	
    	// 빙산을 녹인다.
        int qsize = q.size();
        vector<vector<bool>> changed(N, vector<bool>(M, false));
        for(int i=0; i<qsize; i++)
        {
            auto p = q.front();
            q.pop();
            int y = p.first;
            int x = p.second;
            int water = 0;
            for(int j=0; j<4; j++)
            {
                int ny = y + dy[j];
                int nx = x + dx[j];
                if(0 > ny || ny > N | 0 > nx || nx > M) continue;
                if(v[ny][nx] == 0 && !changed[ny][nx]) water++;
            }
            if(v[y][x] - water <= 0) 
            {
            	v[y][x] = 0;
            	changed[y][x] = true;
            }
            else 
            {
            	v[y][x] -= water;
            	q.push({y,x});
            }
        }
        answer++;
    }
    
    if(separated) printf("%d", answer);
    else printf("0");
    
    return 0;
}

고찰

그래프 탐색 문제를 풀면서 쌓았던 기본기를 확인하는 느낌의 문제였다. 문제에서 요구하는 것이 명확해서 어렵진 않았지만 구현에는 꽤 시간이 걸렸다.