C++로 해결하는 2D 바이너리 배열의 최적 만남의 장소 문제

이번 글에서 살펴볼 문제는 0과 1로만 이루어진 2차원 바이너리 배열입니다. 여기서 값 1은 그룹에 속한 사람의 집 위치를 나타냅니다. 그룹원들이 한 곳에 모여 만나려 할 때, 모든 사람이 이동해야 하는 총 거리를 최소화하는 만남의 장소를 찾아야 하며, 만남의 장소는 집이 아닌 위치라면 배열 내 어디든 가능합니다.

격자 위에서의 최소 이동 거리를 계산할 때 널리 사용되는 것이 맨해튼 거리(Manhattan Distance)입니다. 상하좌우 방향으로만 이동할 수 있다고 가정할 때, 두 점 p1과 p2 사이의 거리는 다음과 같이 정의됩니다.

distance(p1, p2) = |p2.x − p1.x| + |p2.y − p1.y|

예시로 이해하기

입력:
    {10001}
    {00000}
    {00100}

출력: 6

위 예시에서 최적의 만남의 장소는 (0, 2)입니다. 세 집에서 이 지점까지의 거리가 각각 2씩이므로 총 이동 거리는 6(2 + 2 + 2)이 됩니다.

해결 아이디어

핵심은 1로 표시된 모든 지점의 중간 지점, 즉 중앙값(median)을 찾는 것입니다. 수평선 위의 여러 점까지 거리의 합은 그 점들의 중앙값에서 최소가 되므로, 행 좌표와 열 좌표를 분리해 각각의 중앙값을 구하면 됩니다. 맨해튼 거리는 x축 성분과 y축 성분이 서로 독립적으로 계산되기 때문에 이 방법이 성립합니다.

단, 열 좌표는 배열을 순서대로 탐색할 때 정렬되지 않은 상태로 저장되므로, 중앙값을 구하기 전에 반드시 정렬 과정이 필요합니다.

알고리즘 단계

1단계 : 1로 표시된 지점들의 행(row) 좌표와 열(column) 좌표를 각각 별도의 벡터에 저장한다.
2단계 : 두 벡터를 정렬한 뒤 각각의 중앙값을 구해 (midx, midy)를 만남의 장소로 정한다.
3단계 : 모든 1 지점부터 (midx, midy)까지의 맨해튼 거리를 계산한다.
4단계 : 모든 거리의 합을 반환한다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
#define ROW 3
#define COL 5

int minMeetingDistance(int grid[][COL]) {
    if (ROW == 0 || COL == 0)
        return 0;

    vector<int> rows;   // 1의 행 좌표 저장
    vector<int> cols;   // 1의 열 좌표 저장

    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (grid[i][j] == 1) {
                rows.push_back(i);
                cols.push_back(j);
            }
        }
    }

    // 좌표 목록을 정렬한 뒤 중앙값(중간 지점)을 구한다
    sort(rows.begin(), rows.end());
    sort(cols.begin(), cols.end());

    int mid = rows.size() / 2;
    int midx = rows[mid];
    int midy = cols[mid];

    // 모든 집에서 만남의 장소까지의 거리 합을 계산한다
    int totalDistance = 0;
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++)
            if (grid[i][j] == 1)
                totalDistance += abs(midx - i) + abs(midy - j);

    return totalDistance;
}

int main() {
    int grid[ROW][COL] =
    {{1, 0, 1, 0, 1},
     {0, 0, 0, 1, 0},
     {0, 1, 1, 0, 0}};

    cout << "만남을 위해 이동해야 하는 최소 거리는 " << minMeetingDistance(grid);
    return 0;
}

실행 결과

만남을 위해 이동해야 하는 최소 거리는 11

복잡도 분석

배열 전체를 두 번 순회하므로 시간 복잡도는 O(R × C)입니다. 또한 1의 개수를 K라 할 때, 좌표 저장과 정렬에 추가로 O(K log K)의 비용이 듭니다.