[C++] 백준 온라인 저지 2573번 빙산 풀이

하나였던 빙산이 녹아서 쪼개지는 데 최소 몇 년이 걸리는지 구하는 문제

 

---

문제

 

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

 

	2	4	5	3
	3		2	5	2
	7	6	2	4

그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보

 

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

 

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

 

		2	4	1
	1		1	5
	5	4	1	2

그림 2

 

			3
				4
	3	2

그림 3

 

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

 

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

 

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

 

 

풀이 과정

 

 BFS로 탐색하는 횟수가 2번 이상이면 빙산이 둘로 쪼개진 것이니까 그 순간에 탐색을 중단하고 년수를 출력하면 될 거라고 생각했는데 중간에 예외처리를 제대로 하지 않았더니 계속 틀려서 푸는 데 시간이 좀 걸렸습니다 ㅠ.ㅠ

 

 이 문제를 풀 때 주의사항은 BFS/DFS로 탐색하는데 빙산이 모두 녹을 때까지 빙산이 두개 이상으로 쪼개지지 않으면 0을 출력하는 것입니다. 여기서 알 수 있는 것은 뭐다? 매번 탐색할 때마다 빙산이 모두 녹았는가 아닌가를 확인하는 함수가 필요하다...! 그리고 BFS/DFS가 2번 이상 호출되었는지를 확인할 변수와 몇 년이 흘렀는지 저장할 변수도 필요합니다. 

 그리고 BFS로 탐색하는 동시에 빙산을 녹여주면 안 됩니다. BFS 탐색이 한 번 끝난 후에 모든 빙산을 녹여줘야 문제의 의도에 맞게 빙산 측정을 할 수 있습니다. 여기서 알 수 있는 것은 매 턴마다 빙산을 녹여주는 함수가 필요하다. 그러기 위해서는 BFS/DFS로 탐색하는 동안 인접한 바다가 몇 개인지 확인해서 그 값을 저장할 컨테이너도 필요합니다. 저는 vector<pair<위치, 인접한 바다 갯수>> 벡터로 썼습니다.

 

 이것들을 모두 준비했다면 BFS/DFS 탐색을 시작하는데 BFS/DFS 함수가 2번째 호출되는 순간에 지금까지 경과된 년수를 출력하고 종료합니다. 

 BFS/DFS 함수가 2번 이상 호출되지 않고 모든 탐색이 끝났다면 년수를 증가시키고 모든 빙산을 녹여줍니다. 그 후 모든 빙산이 녹았는지 확인 후 빙산이 모두 녹았는데 BFS/DFS 함수가 1번만(2번 미만으로) 호출되었다면 빙산이 한 번도 쪼개지지 않은 것이므로 0을 출력하고 종료합니다. 

 아직 다 녹지 않았다면 아까전의 과정을 다시 반복합니다. 

 

 

코드

 

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

using namespace std;

int height, width;
vector<vector<int>> dir; //방향값 저장용 벡터
vector<vector<int>> ocean; //입력으로 주어지는 바다 벡터 
vector<pair<pair<int, int>, int>> meltingPostions; //녹여야 하는 위치와 그 갯수 
void bfs(pair<int, int> start, vector<vector<bool>>& visited)
{
    queue<pair<int, int>> q;
    q.emplace(start);
    visited[start.first][start.second] = true;
    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        
        int oceanCount = 0;
        for (auto d : dir)
        {
            auto next = make_pair(cur.first + d.front(), cur.second + d.back());
            
            //다음 위치가 바다라면 바다 갯수를 센다. 
            if (0 == ocean[next.first][next.second])
                oceanCount++;
            
            //바다가 아니면 bfs 탐색 
            if (!visited[next.first][next.second] &&
                0 != ocean[next.first][next.second])
            {
                visited[next.first][next.second] = true;
                q.emplace(next);
            }
        }
        
        //만약 바다가 인접해 있었다면 녹여야 할 리스트에 추가한다. 
        if (0 < oceanCount)
            meltingPostions.emplace_back(make_pair(cur, oceanCount));
    }
}

//빙산 녹이는 함수
void MeltIsland()
{
    //녹여야 하는 빙산만 그 갯수만큼 녹인다. 
    for (auto elem : meltingPostions)
    {
        auto pos = elem.first;
        ocean[pos.first][pos.second] -= elem.second;
        //빙산 값이 음수가 되지 않도록 예외처리 
        if (0 > ocean[pos.first][pos.second])
            ocean[pos.first][pos.second] = 0;
    }
}

//빙산이 모두 녹았는지 확인하는 함수 
bool isMelted()
{
    for (int i = 1; height - 1 > i; i++)
    {
        for (int j = 1; width - 1 > j; j++)
        {
            //하나라도 0보다 크면 녹지 않은 빙산이 있는 것 
            if (0 < ocean[i][j])
                return false;
        }
    }
    
    //반복문이 무사히 끝났다면 모든 빙산이 녹은 것이다. 
    return true;
}

int main()
{
    dir.push_back({1,0});
    dir.push_back({-1,0});
    dir.push_back({0,1});
    dir.push_back({0,-1});
    
    cin >> height >> width;
    
    ocean.assign(height, vector<int>(width, 0));
    for (int i = 0; height > i; i++)
    {
        for (int j = 0; width > j; j++)
            cin >> ocean[i][j];
    }
    
    int year = 0;
    while (true)
    {
        int bfsCallCount = 0;
        vector<vector<bool>> visited(height, vector<bool>(width, false));
        meltingPostions.clear();
        for (int i = 1; visited.size() - 1 > i; i++)
        {
            for (int j = 1; visited[i].size() - 1 > j; j++)
            {
                if (!visited[i][j] && 0 != ocean[i][j])
                {
                    bfsCallCount++;
                    //bfs가 2번 이상 호출되는 즉시 현재 년수를 출력하고 프로그램을 종료한다. 
                    if (2 <= bfsCallCount)
                    {
                        cout << year;
                        return 0;
                    }
                    
                    bfs(make_pair(i, j), visited);
                }
            }
        }
        //매 턴이 끝나면 빙산 녹이고 년수 증가 
        MeltIsland();
        year++;
        
        //모든 빙산이 녹았는데 bfs도 2번 미만으로 호출되었으면 0 출력 후 종료 
        if (1 >= bfsCallCount && isMelted())
        {
            cout << 0;
            return 0;
        }
    }
    
    return 0;
}