[ 백준 2573 ] 빙산 (C++)

백준의 빙산(2573) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 먼저 문제의 핵심인 빙산의 갯수를 Count하는 법을 생각해보자. 빙산의 갯수를 Count하는 법은 BFS혹은 DFS 함수를

   호출하는 횟수일 것이다. (본인은 BFS로 풀이)

   입력으로 주어지는 맵에서 0이 아니면서 아직 방문하지 않은 정점에서 BFS를 호출한다고 생각해보자.

   BFS함수 안에서는 0이 아닌 지점에 대해서만 계속해서 탐색을 하며 진행되고, 연결되어 있는 정점들은 모두 방문했다고

   표시가 될 것이다.

   즉, BFS함수가 한번 호출되고 종료되면 빙산의 갯수가 1개라는 것이다.

2. 그럼 이제 본격적인 문제 풀이로 들어가보자. 문제를 해결하기 위해 구현해야 할 내용을 정리해보자.

   1. 빙산의 갯수 Count

     1-1) 빙산의 갯수가 2개 이상이라면 년도 출력 후 종료

     1-2) 빙산의 갯수가 0개 라면 0 출력 후 종료

     1-3) 빙산의 갯수가 1개 라면 2번 실행

   2. 바닷물과 접해있는 빙산들을 바닷물과 접해있는 칸 수 만큼 녹이기

   사실 구현해야 할 내용은 위의 2가지 밖에 없다. 하지만, 위의 2번과정에서 조심해야 할 부분이 하나 있다.

   바닷물과 접해있는 칸 수 만큼 빙산을 녹이는 과정에서, 정점 하나하나 마다 진행하면 안된다.

  

    위의 주어진 맵에서 빨강색으로 표시된 정점에 대해서 살펴보자. 빙산의 높이는 3이고, 주변에 바닷물이 2곳에

    있기 때문에 1년이 지난다면 1이 될 것이다.

    파랑색으로 표시된 정점은 1년이 지난다면 2가 될 것이다.

    하지만, 여기서 저 빨강색과 파랑색 사이에 있는 '2' 인 정점을 보자. 저 정점은 1년후에 0이 될 것이다.

  

    만약에, 여기서 정점 하나하나 마다 값을 계속 바꾼다고 생각해보자. 위에서 말한 '2'인 정점은 0이 될 것이고,

    그 이후에 빨강 정점은 주변에 0이 3개가 있으므로 1년후에 값이 0으로 바뀌게 되는 오류를 범할 수 있다.

    따라서, 기존의 맵을 냅두고, 1년후의 맵을 저장할 새로운 맵이 하나 더 필요하다.

  

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 300
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
int C_MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void BFS(int a, int b)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (Visit[nx][ny] == false && MAP[nx][ny] != 0)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
int Melt(int x, int y)
{
    int Cnt = 0;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (MAP[nx][ny] == 0) Cnt++;
    }
    return Cnt;
}
 
void Solution()
{
    int Year = 0;
    while (1)
    {
        int Land_Cnt = 0;
        memset(Visit, false, sizeof(Visit));
        memset(C_MAP, 0, sizeof(C_MAP));
        
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (MAP[i][j] != 0 && Visit[i][j] == false)
                {
                    Land_Cnt++;
                    BFS(i, j);
                }
            }
        }
 
        if (Land_Cnt >= 2) { cout << Year << endl; break; }
        if (Land_Cnt == 0) { cout << 0 << endl; break; }
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (MAP[i][j] != 0)
                {
                    C_MAP[i][j] = MAP[i][j] - Melt(i, j);
                    if (C_MAP[i][j] < 0) C_MAP[i][j] = 0;
                }
            }
        }        
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                MAP[i][j] = C_MAP[i][j];
            }
        }
 
        Year++;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}