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

📕문제

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 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을 출력한다.

---

💡문제해석

문제를 읽으면 DFS를 사용해야 하는지 BFS를 사용해야 하는지 판단할 줄 알아야 한다.

문제를 잘 읽어보면 구하려는 바가 빙하가 2덩어리 이상으로 분리되는 최소의 년을 구하는 것이다. 

최솟값?! -> BFS라고 생각하면 된다. [확신을 못하지만 거의 다 그렇다..ㅎ]

 

✋주의해야 할 점

큐에 빙산의 위치를 넣는다. 그러고 하나씩 큐에서 pop 하면서 바람을 적용시킨다. 하지만 모든 얼음이 동시에 바람에 영향을 받아야 하는데 이런 방식으로 하나하나씩 하면 적절하지 않은 답이 나온다. 이 점을 잘 해결해야 한다.

---

👀구현

1. 변수 선언

• ice는 빙산과 바다를 입력하는 배열
• visit는 해당 년초에 이 자리가 빙산인지, 바다인지 체크하기 위함.
• fact는 빙산의 개수를 계산할때 사용
• 자세한 설명들은 아래 구현에서 설명할예정이담.

2. 방향 선언

• 문제 설명에서 바람은 왼쪽, 오른쪽, 아래, 위에서 불어오는 것을 알 수 있다. [오른쪽, 왼쪽, 아래, 위]

3. 빙산 넣기

 

• num이 0이 아니라면 빙산이라는 뜻이므로 큐에 좌표를 넣어주고, 빙산이라는 사실을 visit배열로 체크해준다.

4.BFS함수

• size는 바람 불기 전의 빙하의 개수, Size는 바람을 맞는 빙하의 수이다.
  • Size와 size가 같다면 1년이 지난 것이다.
• 큐에서 pop을 하고 해당 좌표를 4가지의 방향으로 움직임.
  • 만약 잘못된 좌표라면 continue.
• 움직인 후에 그 좌표가 바다이고, 지금 내 기준 좌표에 빙산이 아직 남아있고, 움직인 좌표가 처음부터 바다인 곳이라면
  • 기준 좌표에 빙산을 한층 깎아준다.
• 4가지 방향으로 이동한 뒤 만약 빙산이 사라지지 않고 남아있다면 다시 큐에 좌표를 푸시한다.

• Size와 size가 같아질 때 연도가 바뀐다는 것을 위에서 설명했다.
• 그럼 년도를 더해주고, size와 Size를 다시 최신화해준다.
• 이제 빙산의 개수를 체크해줄 것이다.
  • 행렬 전체를 탐색하는데 만약 바다라면 visit값을 0으로 바꿔준다.
  • 여기서 fact라는 배열이 등장하는데 fact는 내가 빙산의 개수를 계산할 때 해당 땅을 밟았는지의 여부를 체크하는 것이다. [자세한 것은 checkice함수 내에서 설명할 예정이다]
• 만약 빙산의 개수[Icenum]가 2 이상이라면 그때의 연도가 답이고 출력하면 된다.
• 만약 빙산의 개수가 2개가 안 나왔다면 fact배열을 0으로 초기화해주고, 빙산의 개수를 다시 0으로 바꿔준다.

• fact배열은 모두 0으로 초기화되어있다.
• 빙하의 개수는 상, 하, 좌, 우로 연결되어있다면 하나로 계산한다.
• row, col을 기준으로 4가지 방향을 탐색하는데 움직인 좌표가 빙하고, 아직 밟지 않은 곳이라면 재귀 문으로 이동한 좌표를 다시 실행한다.
• 하나의 지점을 잡고 움직일 수 있는 모든 좌표를 방문한 뒤, 방문처리를 해주고를 반복하면 빙산의 개수를 구할 수 있을 것이다.

---

코드

/*
백준 2573 골드4 빙산
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
int n, m, day = 0, Icenum = 0, answer = 0;
vector<vector<int>> ice;
vector<vector<int>> visit;
vector<vector<int>> fact;
queue<pair<int, int>> q;
vector<int> result;
vector<int> x = {0, 0, 1, -1}, y = {1, -1, 0, 0};
void bfs();
void checkice(int row, int col);
int main()
{
    cin >> n >> m;
    ice.resize(n, vector<int>(m, 0));
    visit.resize(n, vector<int>(m, 0));
    fact.resize(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int num;
            cin >> num;
            ice[i][j] = num;
            if (num != 0)
            {
                q.push(make_pair(i, j));
                visit[i][j] = 1; //빙산이 있는 곳은 1을 넣어줌.
            }
        }
    }
    bfs();
}
void bfs()
{
    int size = q.size();
    int Size = 0;
    while (q.empty() == 0)
    { //빌떄까지 반복

        int row, col;
        row = q.front().first, col = q.front().second;
        q.pop();
        Size++; //빙산하나 처리했다.
        for (int i = 0; i < 4; i++)
        {
            int dx = row + x[i], dy = col + y[i];
            if (dx < 0 || dx >= n || dy < 0 || dy >= m) //못가는 경우는 continue
            {
                continue;
            }
            if (ice[dx][dy] == 0 && ice[row][col] != 0 && visit[dx][dy] == 0)
            {                    //이동한곳이 바다고, 해당 공간이 빙산일때,visit은 년초에 그 장소가 빙산인지 바다인지를 뜻함.
                ice[row][col]--; //빙산을 깎는다.
            }
        }
        if (ice[row][col] != 0) //바람이 불었는데 빙산이 살아남았다면 큐에 넣어줌.
        {
            q.push(make_pair(row, col));
        }

        if (Size == size) //만약 초기 큐에 있는 빙산의 개수만큼 뺏다면 년차가 바뀌어야함.
        {
            day++;           //년차증가
            size = q.size(); //년차 바뀠으니 변수를 다시 초기화해줌.
            Size = 0;
            // cout << "now year : " << day << endl;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (ice[i][j] == 0)
                    {
                        visit[i][j] = 0;
                        continue;
                    }
                    if (fact[i][j] == 0)
                    {
                        checkice(i, j);
                        Icenum++;
                    }
                }
            }
            if (Icenum >= 2)
            {
                answer = day;
                break;
            }
            fact.assign(n, vector<int>(m, 0));
            Icenum = 0;
        }
    }
    cout << answer << endl;
}
void checkice(int row, int col)
{
    if (fact[row][col] == 0)
    { //검사안했다.
        fact[row][col] = 1;
        for (int i = 0; i < 4; i++)
        {
            int dx = row + x[i], dy = col + y[i];
            if (dx < 0 || dx >= n || dy < 0 || dy >= m)
            {
                continue;
            }

            if (ice[dx][dy] != 0 && fact[dx][dy] == 0)
            { //빙산이 있다.
                checkice(dx, dy);
            }
        }
    }
}

---

✔느낀 점

• 원래 있던 빙하가 녹아서 다른 빙하에 영향을 주는 사실을 인지를 하는 것이 중요했고, 그것을 코드화 하는 것이 문제의 관건이다.
  • 조금 더 간결하게 하고 싶었지만, 배열을 여러 개 사용하는 안 좋은 습관을 사용한 것 같다.
• 빙하의 개수를 계산하는 함수는 잘 짠 것 같다.
• 문제는 BFS를 바로 찾아냈다면 쉽게 풀 수 있는 문제이다.