[백준 2638] 치즈 (C#, C++) - soo:bak

문제 링크

2638번 - 치즈

설명

격자에 치즈가 있고, 외부 공기와 2면 이상 접촉한 치즈는 한 시간 후에 녹습니다. 모든 치즈가 녹는 데 걸리는 시간을 구하는 문제입니다.

접근법

이 문제에서 중요한 점은 외부 공기와 내부 공기를 구분하는 것입니다. 치즈 내부에 있는 빈 칸은 공기가 아니라 치즈로 둘러싸인 공간이므로, 이 빈 칸과 접촉해도 치즈가 녹지 않습니다.

외부 공기를 찾기 위해 격자의 가장자리에서 BFS를 수행합니다. 문제 조건상 가장자리에는 치즈가 없으므로 (0, 0)에서 시작하면 됩니다. BFS로 빈 칸을 탐색하면서 치즈를 만나면 해당 치즈의 접촉 횟수를 1 증가시킵니다. 같은 치즈를 여러 방향에서 만날 수 있으므로 접촉 횟수가 2 이상이 될 수 있습니다.

BFS가 끝나면 접촉 횟수가 2 이상인 치즈를 모두 녹입니다. 치즈가 녹으면 내부 공간이 외부와 연결될 수 있으므로, 다음 시간에는 다시 외부 공기를 탐색해야 합니다.

이 과정을 치즈가 모두 사라질 때까지 반복하고, 반복 횟수를 답으로 출력합니다.

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static int R, C;
    static int[,] board = new int[100, 100];
    static readonly int[] dr = { -1, 1, 0, 0 };
    static readonly int[] dc = { 0, 0, -1, 1 };

    static bool MeltStep() {
      var expo = new int[R, C];
      var vis = new bool[R, C];
      var q = new Queue<(int r, int c)>();
      q.Enqueue((0, 0));
      vis[0, 0] = true;

      while (q.Count > 0) {
        var (r, c) = q.Dequeue();
        for (var d = 0; d < 4; d++) {
          var nr = r + dr[d];
          var nc = c + dc[d];
          if (nr < 0 || nr >= R || nc < 0 || nc >= C)
            continue;
          if (board[nr, nc] == 1) {
            expo[nr, nc]++;
          } else if (!vis[nr, nc]) {
            vis[nr, nc] = true;
            q.Enqueue((nr, nc));
          }
        }
      }

      var melted = false;
      for (var r = 0; r < R; r++) {
        for (var c = 0; c < C; c++) {
          if (board[r, c] == 1 && expo[r, c] >= 2) {
            board[r, c] = 0;
            melted = true;
          }
        }
      }
      return melted;
    }

    static void Main(string[] args) {
      var first = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      R = first[0];
      C = first[1];
      for (var r = 0; r < R; r++) {
        var line = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        for (var c = 0; c < C; c++)
          board[r, c] = line[c];
      }

      var time = 0;
      while (true) {
        var melted = MeltStep();
        if (!melted)
          break;
        time++;
      }
      Console.WriteLine(time);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

int R, C;
int board[100][100];
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

bool meltStep() {
  int expo[100][100] = {};
  bool vis[100][100] = {};
  queue<pii> q;
  q.push({0, 0});
  vis[0][0] = true;

  while (!q.empty()) {
    auto [r, c] = q.front(); q.pop();
    for (int d = 0; d < 4; d++) {
      int nr = r + dr[d];
      int nc = c + dc[d];
      if (nr < 0 || nr >= R || nc < 0 || nc >= C)
        continue;
      if (board[nr][nc] == 1) {
        expo[nr][nc]++;
      } else if (!vis[nr][nc]) {
        vis[nr][nc] = true;
        q.push({nr, nc});
      }
    }
  }

  bool melted = false;
  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      if (board[r][c] == 1 && expo[r][c] >= 2) {
        board[r][c] = 0;
        melted = true;
      }
    }
  }
  return melted;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> R >> C;
  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++)
      cin >> board[r][c];
  }

  int time = 0;
  while (meltStep())
    time++;

  cout << time << "\n";

  return 0;
}