[BOJ/2638/C++] 치즈

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

문제

• N×M의 모눈종이 위에 아주 얇은 치즈가 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다.

• 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다.

• 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

조건

• 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다.
• 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다.
• 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

풀이

바깥공기와 안의 공기를 구분해주는 아이디어를 금방 떠올려서, 코드는 길지만 생각보다 짜는데는 어렵지 않은 문제였다.

안과 밖 구분해주기

가장자리는 무조건 바깥공기이기 때문에, 가장자리에서 시작해서 bfs를 돌면서 바깥공기인 친구들을 방문배열에 체크한다. 그리고, 치즈인 것들도 방문체크한다. 그러면 남은 친구들은 안쪽 공기가된다.

이렇게 해서, 배열 한개를 더 만들어서, chk_board라는 걸 기준으로 치즈를 녹여주고, board를 업데이트 하는 과정을 가졌다.

안과 밖 구분해주기 2 (다른 블로그 코드 보면서, 좋은 아이디어라고 생각)

안과 밖을 구분해줄 때, 바깥공기를 기준으로 BFS를 돌리기 때문에, 어짜피 BFS로 닿지 않은 곳은 안쪽공기이다.
그러므로, 해당 Queue가 빌 때 까지만 반복을 돌면 된다. 그리고, 녹을 수 있는 치즈를 확인해주는 과정까지 합쳐버린다면 훨씬 코드는 간결해질 수 있다.

#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[101][101];
int chk_board[101][101];
int cnt = 0;
bool visited[101][101];

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

void bfs(int x, int y)
{
  queue<pair<int, int>> Q;
  Q.push({x, y});
  chk_board[x][y] = 0;
  visited[x][y] = true;

  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])
      {
        visited[nx][ny] = true;
        chk_board[nx][ny] = 0;
        Q.push({nx, ny});
      }
    }
  }
}

void initVisited()
{
  for (int i = 0; i < N; i++)
    fill(visited[i], visited[i] + M, false);
}

void chk_InnerAir()
{
  // 가장자리를 시작하면, 얘는 무조건 바깥공기임.(치즈 x 내부공기 x)
  // 바깥공기
  bfs(0, 0);
  // 치즈
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      if (board[i][j] == 1)
      {
        visited[i][j] = true;
        chk_board[i][j] = 1;
      }
    }
  }
  // 안의 공기
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      if (!visited[i][j])
        chk_board[i][j] = 2;
}
void meltCheese()
{
  vector<pair<int, int>> melt_pos;

  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      if (chk_board[i][j] == 1)
      {
        int tmp = 0;
        for (int dir = 0; dir < 4; dir++)
        {
          int nx = i + dx[dir];
          int ny = j + dy[dir];
          if (chk_board[nx][ny] == 0)
            tmp++;
        }
        if (tmp >= 2)
          melt_pos.push_back({i, j});
      }
    }
  }

  for (int i = 0; i < melt_pos.size(); i++)
    board[melt_pos[i].X][melt_pos[i].Y] = 0;
}
bool AllDone()
{
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      if (board[i][j] == 1)
        return false;
    }
  }
  return true;
}
void solve()
{
  while (true)
  {
    if (AllDone())
    {
      cout << cnt << '\n';
      return;
    }
    initVisited();
    chk_InnerAir();
    // 치즈를 녹여준다.
    meltCheese();
    cnt++;
  }
}

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

  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      cin >> board[i][j];
  solve();

  return 0;
}