C++로 푸는 벽과 게이트(Walls and Gates) 문제 – BFS 최단 거리 알고리즘

m × n 크기의 2차원 격자(grid)가 하나 주어지며, 이 격자는 다음 세 가지 값 중 하나로 초기화되어 있다고 가정합니다.

• -1: 벽 또는 장애물
• 0: 게이트(gate)
• INF: 무한대를 뜻하며, 빈 방(empty room)을 의미합니다.

여기서 INF는 2³¹ − 1 = 2147483647이며, 게이트까지의 거리는 항상 2147483647보다 작다고 가정할 수 있습니다. 목표는 각 빈 방을 가장 가까운 게이트까지의 거리로 채우는 것입니다. 만약 어떤 방에서 게이트에 도달하는 것이 불가능하다면, 해당 방은 INF 값을 그대로 유지해야 합니다.

예제로 이해하기

입력이 아래와 같다면,

출력은 다음과 같습니다.

접근 방법: 너비 우선 탐색(BFS)

이 문제는 BFS(너비 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 모든 게이트를 시작점으로 큐에 넣고, 레벨(level) 단위로 인접한 방을 한 칸씩 확장해 나가는 것입니다. 이렇게 하면 각 방에는 자연스럽게 가장 가까운 게이트까지의 최단 거리가 기록됩니다.

알고리즘 단계

1. 4방향 이동을 나타내는 배열 dir(크기 4 × 2)을 {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}로 정의합니다.
2. n := rooms의 행(row) 개수
3. m := n이 0이 아니면 열(column) 개수, 그렇지 않으면 0
4. 좌표 쌍(pair)을 저장할 큐 q를 선언합니다.
5. 격자 전체를 순회하면서 rooms[i][j] == 0인 모든 게이트 위치를 큐에 삽입합니다.
6. 큐가 비어 있지 않은 동안 lvl := 1부터 레벨을 1씩 증가시키며 반복합니다.
   • sz := 현재 큐의 크기
   • sz번만큼 반복하면서 큐의 맨 앞 원소 curr을 꺼냅니다(pop).
   • x := curr.first, y := curr.second
   • 네 방향 각각에 대해 새 좌표 nx := x + dir[i][0], ny := y + dir[i][1]을 계산합니다.
   • nx < 0 또는 ny < 0 또는 nx ≥ n 또는 ny ≥ m 또는 rooms[nx][ny] < lvl이면 다음 반복으로 건너뜁니다. (벽이나 이미 더 짧은 거리가 기록된 방은 재방문하지 않습니다.)
   • rooms[nx][ny] := lvl로 갱신하고, {nx, ny}를 큐에 삽입합니다.

이 알고리즘의 시간 복잡도는 O(m × n)입니다. 각 칸은 최대 한 번만 큐에 들어가 처리되기 때문이며, 공간 복잡도 역시 큐에 저장되는 좌표 개수에 비례해 O(m × n)입니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
   void wallsAndGates(vector<vector<int>>& rooms) {
      int n = rooms.size();
      int m = n ? rooms[0].size() : 0;
      queue<pair<int, int> > q;
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            if (rooms[i][j] == 0)
               q.push({ i, j });
         }
      }
      for (int lvl = 1; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            pair<int, int> curr = q.front();
            q.pop();
            int x = curr.first;
            int y = curr.second;
            for (int i = 0; i < 4; i++) {
               int nx = x + dir[i][0];
               int ny = y + dir[i][1];
               if (nx < 0 || ny < 0 || nx >= n || ny >= m || rooms[nx][ny] < lvl)
                  continue;
               rooms[nx][ny] = lvl;
               q.push({ nx, ny });
            }
         }
      }
   }
};
main(){
   vector<vector<int>> v = {{2147483647,-1,0,2147483647}, {2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647,-1}, {0,-1,2147483647,2147483647}};
   Solution ob;
   ob.wallsAndGates(v);
   print_vector(v);
}

실행 결과

입력

{{2147483647,-1,0,2147483647},{2147483647,2147483647,2147483647,-1},{2147483647,-1,2147483647,-1},{0,-1,2147483647,2147483647}}

출력

[[3, -1, 0, 1],[2, 2, 1, -1],[1, -1, 2, -1],[0, -1, 3, 4]]