문제 개요
각 원소가 [x, y] 형태의 유클리드 좌표를 나타내는 좌표 목록이 주어졌다고 가정해 봅시다. 이때 우리가 구해야 하는 것은 주어진 좌표들 중 임의의 두 점에 대한 가장 작은 제곱 거리, 즉 (x1 - x2)2 + (y1 - y2)2의 최솟값입니다.
예를 들어 입력이 coordinates = {{1, 2}, {1, 4}, {3, 5}}라면, 점 (1, 2)와 (1, 4) 사이의 제곱 거리가 4로 가장 작으므로 출력은 4가 됩니다.
해결 접근 방법
모든 점 쌍을 일일이 비교하는 O(n²) 완전 탐색 대신, 배열을 정렬한 뒤 map 자료구조를 활용하면 불필요한 비교를 줄여 더 효율적으로 문제를 해결할 수 있습니다. 알고리즘은 다음과 같은 단계로 진행됩니다.
- y 좌표를 키(key)로, 해당 y 값에서 가장 오른쪽에 있는 x 좌표를 값(value)으로 저장하는 맵 ytorightmostx를 정의합니다.
- 좌표 배열을 오름차순으로 정렬합니다.
- 결과값 ret을 무한대에 해당하는 매우 큰 값으로 초기화합니다.
- 각 점 p에 대해 다음을 수행합니다.
- it = ytorightmostx에서 (p[1] - sqrt(ret))보다 크거나 같은 첫 번째 원소의 위치(lower_bound)를 찾습니다.
- it가 ytorightmostx의 마지막 원소가 아닌 동안 아래 과정을 반복합니다.
- yd = it의 첫 번째 값(y) - p[1]
- yd > 0이고 yd * yd >= ret이라면, 더 이상 더 가까운 점이 없으므로 반복문을 종료합니다.
- nxt = it의 다음 반복자
- ret = ret와 dist(p[0], p[1], it의 첫 번째 값, it의 두 번째 값) 중 최솟값으로 갱신
- xd = it의 두 번째 값(x) - p[0]
- xd * xd >= ret이라면, 이후 점들과의 거리는 항상 ret 이상이므로 it를 ytorightmostx에서 삭제합니다.
- it = nxt로 이동하여 다음 원소를 검사합니다.
- ytorightmostx[p[1]] = p[0]으로 현재 점을 맵에 저장합니다.
- 최종 결과 ret을 반환합니다.
여기서 사용되는 dist() 함수는 네 개의 매개변수 xl, yl, xr, yr을 받아 두 점 사이의 제곱 거리 xd * xd + yd * yd를 계산하여 반환합니다. 실제 거리의 제곱만 비교하면 되기 때문에 sqrt 연산 없이 정수 연산만으로 정확한 결과를 얻을 수 있습니다.
예제 코드
다음 구현을 통해 위 알고리즘을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
long long dist(long long xl, long long yl, long long xr, long long yr) {
long long xd = xl - xr;
long long yd = yl - yr;
return xd * xd + yd * yd;
}
int solve(vector<vector<int>>& coordinates) {
map<long long, long long> ytorightmostx;
sort(coordinates.begin(), coordinates.end());
long long ret = 1e18;
for (auto& p : coordinates) {
auto it = ytorightmostx.lower_bound(p[1] - sqrt(ret));
while (it != ytorightmostx.end()) {
long long yd = it->first - p[1];
if (yd > 0 && yd * yd >= ret) {
break;
}
auto nxt = it;
nxt++;
ret = min(ret, dist(p[0], p[1], it->second, it->first));
long long xd = (it->second - p[0]);
if (xd * xd >= ret) {
ytorightmostx.erase(it);
}
it = nxt;
}
ytorightmostx[p[1]] = p[0];
}
return ret;
}
int main(){
vector<vector<int>> coord = {{1, 2},{1, 4},{3, 5}};
cout << solve(coord) << endl;
return 0;
}
입력
{{1, 2},{1, 4},{3, 5}}출력
4
정리
이 알고리즘은 좌표를 x 기준으로 정렬한 후, 현재까지의 최소 제곱 거리 ret을 이용해 탐색 범위를 y축 방향으로 sqrt(ret) 이내로 제한함으로써 비교 횟수를 크게 줄입니다. 또한 x 방향으로도 이미 ret 이상 떨어진 점들은 맵에서 제거하여 이후 계산에서 제외시킵니다. 그 결과, 평균적으로 완전 탐색보다 훨씬 적은 연산으로 두 점 사이의 최소 제곱 거리를 구할 수 있습니다.