C++로 풀어보는 모든 건물까지의 최단 거리 문제

문제 소개

빈 땅 위에 집을 하나 짓고자 할 때, 이 집에서 모든 건물까지의 이동 거리의 합이 최소가 되는 위치를 찾아야 합니다. 이동은 상·하·좌·우 네 방향으로만 가능하며, 값이 0, 1, 2로 구성된 2D 그리드가 입력으로 주어집니다. 각 값의 의미는 다음과 같습니다.

• 0 : 자유롭게 지나다닐 수 있는 빈 땅

• 1 : 통과할 수 없는 건물

• 2 : 통과할 수 없는 장애물

예를 들어 입력이 아래와 같다고 가정해 보겠습니다.

세 개의 건물이 각각 (0,0), (0,4), (2,2)에 위치하고, 장애물 하나가 (0,2)에 있습니다. 이 경우 (1,2) 지점이 집을 짓기에 가장 이상적인 빈 땅입니다. 세 건물까지의 이동 거리가 각각 3, 3, 1이므로 총합이 3+3+1=7로, 다른 어떤 빈 땅보다도 최소가 되기 때문입니다.

풀이 접근 방법

이 문제는 BFS(너비 우선 탐색)를 이용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 건물에서 출발하는 BFS를 한 번씩 수행하면서, 도달 가능한 모든 빈 땅에 대해 "그 건물까지의 거리"를 누적해 두는 것입니다. 이후 모든 건물에 도달할 수 있는 칸 중에서 누적 거리가 가장 작은 곳을 정답으로 선택합니다.

구체적인 단계는 다음과 같습니다.

1. ret을 무한대(INT_MAX)로 초기화합니다. n은 행의 개수, m은 열의 개수, numberOfOnes는 건물의 개수를 저장합니다.

2. n × m 크기의 2D 배열 두 개를 준비합니다. dist는 각 칸까지의 거리 합을, reach는 해당 칸에 도달한 건물의 수를 기록합니다.

3. 그리드를 순회하다가 값이 1인 칸(건물)을 만나면 다음을 수행합니다.

   • numberOfOnes를 1 증가시킵니다.

   • 큐에 현재 건물의 좌표 {i, j}를 넣고, 이 건물의 BFS 전용 visited 집합을 생성합니다.

   • 레벨(lvl)을 1부터 시작해 BFS를 진행합니다. 큐가 빌 때까지 각 레벨마다 큐에 담긴 원소를 꺼내 상하좌우 네 방향을 확인합니다.

   • 다음 칸(nx, ny)이 그리드 범위를 벗어나거나, 이미 방문했거나, 빈 땅(0)이 아니라면 해당 칸은 건너뜁니다.

   • 조건을 통과한 칸이라면 visited에 추가하고, dist[nx][ny]에 현재 레벨 lvl을 더한 뒤 reach[nx][ny]를 1 증가시키고, 큐에 삽입합니다.

4. 모든 건물에 대한 BFS가 끝나면 그리드를 다시 순회하며, grid[i][j] == 0이면서 reach[i][j] == numberOfOnes인 칸(즉, 모든 건물에 도달 가능한 빈 땅) 중에서 dist[i][j]의 최솟값을 ret에 저장합니다.

5. ret이 여전히 무한대라면 조건을 만족하는 빈 땅이 없다는 의미이므로 -1을, 그렇지 않으면 ret을 반환합니다.

C++ 구현 코드

아래는 위 알고리즘을 C++로 구현한 코드입니다.

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int ret = INT_MAX;
        int n = grid.size();
        int m = grid[0].size();
        int numberOfOnes = 0;
        vector < vector <int> > dist(n, vector <int>(m));
        vector < vector <int> > reach(n, vector <int>(m));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1){
                    numberOfOnes++;
                    queue < pair <int, int> > q;
                    q.push({i, j});
                    set < pair <int, int> > visited;
                    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 k = 0; k < 4; k++){
                                int nx = x + dir[k][0];
                                int ny = y + dir[k][1];
                                if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited.count({nx, ny}) || grid[nx][ny] != 0) continue;
                                visited.insert({nx, ny});
                                dist[nx][ny] += lvl;
                                reach[nx][ny]++;
                                q.push({nx, ny});
                            }
                        }
                    }
                }
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 0 && reach[i][j] == numberOfOnes){
                    ret = min(ret, dist[i][j]);
                }
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};

실행 결과 확인

입력

[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

출력

7

복잡도 분석

그리드의 크기를 n × m이라고 할 때, 각 건물마다 최대 전체 그리드 영역을 탐색하는 BFS를 수행하므로 시간 복잡도는 O((n·m)²)입니다. 공간 복잡도는 dist와 reach 배열, 큐, visited 집합에 의해 결정되며 O(n·m)입니다.