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

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

문제

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

조건

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

풀이

문제를 잘 분리해서 푼다면, 구현자체는 어렵지 않은 문제였다. 이 문제에서 주의해야(?) 신경써야할 점은 2가지 였던것 같다.

• 빙산이 녹는과정을 한 번에 반영을 해주어야 한다는 점. 예를들어, 옆 빙산이 먼저 녹을 수 있는데, 차례대로 빙산이 녹는다면 '물'이된 빙산을 또 세어주면 안된다.
• 애초에 두덩어리 이상 혹은, 모두 녹는경우를 따로 생각해야한다는 점이다.

문제에서 한 덩어리의 빙산이 주어진다고 했으니, 두덩어리 이상인 경우는 제외되고, 모두 녹아서 없어지는 확인을 해주어야한다. 그렇다면, 0을 출력해주어야하기 때문이다.

한 번에 녹는 과정을 반영해주기 위해서, 메모리 공간을 더 써서 2개의 board를 써주었다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define X first
#define Y second

using namespace std;

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

int board[301][301];
int copy_board[301][301];
bool visited[301][301];

bool outOfRange(int x, int y)
{
  return (x < 0 || x >= N || y < 0 || y >= M);
}

void copying_board()
{
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      board[i][j] = copy_board[i][j];
}

void melting()
{
  queue<pair<int, int>> iceberg;

  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      if (board[i][j] > 0)
      {
        iceberg.push({i, j});
      }
    }
  }

  while (!iceberg.empty())
  {
    pair<int, int> cur = iceberg.front();
    iceberg.pop();
    int cnt = 0;
    for (int dir = 0; dir < 4; dir++)
    {
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      // 범위 밖이면, 넘어가고
      if (outOfRange(nx, ny))
        continue;
      if (board[nx][ny] == 0)
        cnt++;
    }
    if (cnt <= board[cur.X][cur.Y])
      copy_board[cur.X][cur.Y] = board[cur.X][cur.Y] - cnt;
    else
      copy_board[cur.X][cur.Y] = 0;
  }
  copying_board();
}

void bfs(int start_x, int start_y)
{
  queue<pair<int, int>> Q;
  visited[start_x][start_y] = true;
  Q.push({start_x, start_y});

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

    for (int dir = 0; dir < 4; dir++)
    {
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if (outOfRange(nx, ny))
        continue;
      if (board[nx][ny] == 0 || visited[nx][ny])
        continue;
      visited[nx][ny] = true;
      Q.push({nx, ny});
    }
  }
}
int chk_iceberg()
{
  int area = 0;
  // init visited array
  for (int i = 0; i < N; i++)
  {
    fill(visited[i], visited[i] + M, false);
  }
  // 연결요소 탐색
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      if (board[i][j] > 0 && !visited[i][j])
      {
        area++;
        bfs(i, j);
      }
    }
  }
  return area;
}

int main()
{
  fastio;
  cin >> N >> M;

  int cnt = 0;
  int ans = 0;

  int tmp;
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      cin >> tmp;
      board[i][j] = tmp;
      copy_board[i][j] = tmp;
    }
  }

  int year = 0;

  while (true)
  {
    // 2개로 나누어 졌는지 확인한다.
    cnt = chk_iceberg();
    // 다 녹은 상태라면
    if (cnt == 0)
    {
      cout << 0 << '\n';
      return 0;
    }
    else if (cnt >= 2)
    {
      cout << year << '\n';
      return 0;
    }
    melting();
    year++;
    // 빙산이 녹는다
  }
  return 0;
}