모든 셀을 검은색으로 바꾸는 데 필요한 반복 횟수를 구하는 C++ 프로그램

검은색 셀과 흰색 셀, 두 종류의 칸으로 이루어진 격자(grid)가 주어졌다고 가정해 봅시다. 검은색 셀은 '#'로, 흰색 셀은 '.'로 표현되며, 격자는 문자열 배열 형태로 입력됩니다. 우리가 수행해야 할 작업은 다음과 같습니다.

검은색 셀과 한 변을 맞대고 있는 흰색 셀을 모두 검은색으로 바꿉니다. 이 연산을 격자의 모든 셀이 검은색이 될 때까지 반복합니다.
격자 전체를 검은색으로 만드는 데 걸리는 반복 횟수를 계산합니다. 단, 처음 상태의 격자에는 반드시 검은색 셀이 하나 이상 존재해야 합니다.

예를 들어 입력이 h = 4, w = 4, grid = {"#...", ".#..", "....", "...#"}라면 다음과 같은 격자가 됩니다.

#	.	.	.
.	#	.	.
.	.	.	.
.	.	.	#

이 경우 출력값은 3입니다. 즉, 모든 셀을 검은색으로 바꾸는 데 세 번의 반복이 필요합니다.

문제 해결 접근 방법

이 문제는 그래프 탐색 기법인 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

처음부터 검은색('#')인 셀들을 모두 시작점으로 삼아 동시에 BFS를 수행합니다(멀티 소스 BFS).
탐색이 진행되면서 각 셀에는 가장 가까운 초기 검은색 셀까지의 거리가 기록되며, 이 거리 값들 중 최댓값이 곧 필요한 반복 횟수가 됩니다.

매 반복마다 검은 영역이 한 칸씩 확장되므로, 특정 셀이 검은색으로 바뀌기까지 걸리는 시간은 그 셀에서 가장 가까운 초기 검은색 셀까지의 거리와 같습니다. 따라서 전체 격자를 채우는 데 필요한 반복 횟수는 모든 셀의 거리 값 중 최댓값입니다.

알고리즘 단계

크기가 4인 배열 dx 정의 := { 1, 0, -1, 0 }
크기가 4인 배열 dy 정의 := { 0, 1, 0, -1 }
2차원 배열 distance 정의
정수 쌍(pair)을 저장하는 큐 q 정의
i := 0에서 시작해 i < h인 동안 i를 1씩 증가시키며 반복:
   j := 0에서 시작해 j < w인 동안 j를 1씩 증가시키며 반복:
      만약 grid[i][j]가 '#'와 같다면:
         distance[i][j] := 0
         q에 쌍(i, j)을 삽입
q가 비어 있지 않은 동안 반복:
   now := q의 맨 앞 원소를 꺼내고 q에서 제거
   dir := 0에서 시작해 dir < 4인 동안 dir을 1씩 증가시키며 반복:
      cx := now의 첫 번째 값 + dx[dir]
      cy := now의 두 번째 값 + dy[dir]
      만약 cx < 0 또는 cx >= h 또는 cy < 0 또는 cy >= w라면:
         건너뜀(continue)
      만약 distance[cx][cy]가 -1과 같다면:
         distance[cx][cy] := distance[now의 첫 번째 값][now의 두 번째 값] + 1
         q에 쌍(cx, cy)을 삽입
ans := 0
i := 0에서 시작해 i < h인 동안 반복:
   j := 0에서 시작해 j < w인 동안 반복:
      ans := ans와 distance[i][j] 중 최댓값
ans 출력

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

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

void solve(int h, int w, vector<string> grid){
   int dx[4] = { 1, 0, -1, 0 };
   int dy[4] = { 0, 1, 0, -1 };
   vector<vector<int>> distance(h, vector<int>(w, -1));
   queue<pair<int, int>> q;
   for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
         if (grid[i][j] == '#') {
            distance[i][j] = 0;
            q.push(pair<int, int>(i, j));
         }
      }
   }
   while (!q.empty()) {
      auto now = q.front();
      q.pop();
      for (int dir = 0; dir < 4; dir++) {
         int cx = now.first + dx[dir];
         int cy = now.second + dy[dir];
         if (cx < 0 || cx >= h || cy < 0 || cy >= w) continue;
         if (distance[cx][cy] == -1) {
            distance[cx][cy] = distance[now.first][now.second] + 1;
            q.push(pair<int, int>(cx, cy));
         }
      }
   }
   int ans = 0;
   for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
         ans = max(ans, distance[i][j]);
      }
   }
   cout << ans << endl;
}
int main() {
   int h = 4, w = 4;
   vector<string> grid = {"#...", ".#..", "....", "...#"};
   solve(h, w, grid);
   return 0;
}

입력

4, 4, {"#...", ".#..", "....", "...#"}