문제 개요
두 명 이상으로 구성된 그룹이 함께 만나려고 하며, 이때 총 이동 거리를 최소화하는 만남 지점을 찾는다고 가정해 봅시다. 0 또는 1의 값을 가지는 2차원 격자(grid)가 주어지고, 값이 1인 칸은 그룹원 중 한 사람의 집 위치를 나타냅니다.
거리 계산에는 맨해튼 거리(Manhattan Distance) 공식을 사용합니다.
distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|
입력 예시
| 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
출력
6
위 행렬에서 세 사람은 각각 (0,0), (0,4), (2,2)에 살고 있습니다. 이때 (0,2)가 가장 이상적인 만남 지점인데, 총 이동 거리가 2 + 2 + 2 = 6으로 최소가 되기 때문입니다.
핵심 아이디어
맨해튼 거리에서는 x좌표와 y좌표가 서로 독립적으로 계산된다는 점이 중요합니다. 따라서 최적의 만남 지점은 각 좌표 축별로 중앙값(median)에 해당하는 위치가 됩니다. 모든 집의 행 좌표와 열 좌표를 각각 모은 뒤, 정렬하여 양 끝에서부터 짝을 지어 거리 차이를 더하면 총 이동 거리를 손쉽게 구할 수 있습니다.
풀이 접근 방법
- 거리 합을 계산하는 함수
get()을 정의합니다. 배열 v를 인자로 받습니다. - 배열 v를 오름차순으로 정렬합니다.
- i := 0, j := v의 크기 - 1, ret := 0으로 초기화합니다.
- i < j인 동안 다음을 반복합니다.
- ret := ret + (v[j] - v[i])
- i를 1 증가시키고, j를 1 감소시킵니다.
- ret을 반환합니다.
- 메인 로직에서는 다음을 수행합니다.
- 행 좌표를 담을 배열 row와 열 좌표를 담을 배열 col을 선언합니다.
- 격자 전체를 순회하면서 grid[i][j]가 0이 아니면 row에 i를, col에 j를 추가합니다.
- 최종적으로
get(row) + get(col)을 반환합니다.
C++ 구현 코드
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
vector<int> row;
vector<int> col;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j]) {
row.push_back(i);
col.push_back(j);
}
}
}
return get(row) + get(col);
}
int get(vector <int> v){
sort(v.begin(), v.end());
int i = 0;
int j = v.size() - 1;
int ret = 0;
while (i < j) {
ret += v[j] - v[i];
i++;
j--;
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}};
cout << (ob.minTotalDistance(v));
}입력
{{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}}출력
6
복잡도 분석
격자의 크기를 m × n이라 할 때, 모든 칸을 한 번씩 순회하므로 시간 복잡도는 O(mn log(mn))입니다(정렬 비용 포함). 공간 복잡도는 집의 개수 k에 대해 좌표를 저장하는 데 O(k)가 필요합니다.