최소 / 최대 맨해튼 거리 (Manhattan Distance)

  1. 맨해튼 거리(Manhattan Distance)란?

 

우리가 일상생활에서, 또는 일반적으로 사용하는 거리는 '유클리드 거리'이다. 편의상 2차원 평면 (x축, y축)이라고 하자.

두 점 $ (x1, y1) $, $ (x2, y2) $ 사이의 거리를 구한다고 할 때, 우리가 일반적으로 이용해왔던 $\sqrt{(x1 - x2)^2 + (y1-y2)^2}$ 로 구하는 거리가 유클리드 거리이다. 

 

반면, 맨해튼 거리(Manhattan Distance)는 각 좌표의 차를 모두 더한 것을 거리로 한다. 

즉, $ \left | x1 - x2 \right | + \left | y1 - y2 \right | $ 가 두 점 $ (x1, y1) $, $ (x2, y2) $ 사이의 맨해튼 거리이다. 

일상생활에서는 잘 이용되지 않지만, 프로그래밍 문제에서는 가끔 나오긴 한다. 

 

맨해튼 거리의 특징은, 두 점 사이의 도로가 모두 x축 또는 y축에 평행한 경우라면, 두 점 사이의 최단거리는 항상 맨해튼 거리와 일치하게 된다는 점이다. 

위 그림에서, 초록색 선은 유클리드 거리를 나타낸다. 

그리고 파란선과 노란선은 모두 시작점에서 끝 점까지 최단 거리로 갈 수 있는 경우들인데, 이 거리들은 모두 결국 맨해튼 거리를 나타내는 빨간 선과 거리가 동일하다. 

 

그리고, 맨해튼 거리는 항상 유클리드 거리보다 크거나 같다는 성질이 있다.  

 

또한, 머신러닝 등의 분야에서 '거리'는 일종의 유사도(Similarity) 개념이기 때문에 두 점 사이의 거리를 구하는 여러 방법들을 많이 이용한다고 한다. 

 

 

  2. 최소 / 최대 맨해튼 거리(Manhattan Distance)

그렇다면, PS적인 관점에서는 여러 점들이 주어졌을 때, 두 점 사이의 거리가 최소 또는 최대인 두 점에 흥미가 생길 것이다. 모든 두 점 쌍들을 비교할 수 없을 만큼 점의 개수가 크다고 가정하자. (N ≥ 10만)

 

유클리드 거리에서는 보통 최소 거리를 구한다면 분할 정복을, 최대 거리를 구한다면 로테이팅 캘리퍼스 알고리즘 등을 생각할 것이다. 

 

하지만 맨해튼 거리에서는 훨씬 간단하다. 

 

두 점 $ (x1, y1) $, $ (x2, y2) $ 사이의 거리가  $ \left | x1 - x2 \right | + \left | y1 - y2 \right | $ 이므로, 네 가지 경우에 따라서 절댓값을 제거해줄 수 있다. 

 

i) $ x1 \geq x2 \; \&\& \; y1 \geq y2 $

 

 $=> \left | x1 - x2 \right | + \left | y1 - y2 \right | $ = $ x1 - x2 + y1 - y2 $ $\;=\;$ $(x1 + y1) - (x2 + y2) $

 

ii) $ x1 \geq x2 \; \&\& \; y1 < y2 $

 

 $=> \left | x1 - x2 \right | + \left | y1 - y2 \right | $ = $ x1 - x2 + y2 - y1 $ $\;=\;$ $(x1 - y1) - (x2 - y2) $

 

iii) $ x1 < x2 \; \&\& \; y1 \geq y2 $

 

 $=> \left | x1 - x2 \right | + \left | y1 - y2 \right | $ = $ x2 - x1 + y1 - y2 $ $\;=\;$ $(x2 - y2) - (x1 - y1) $

 

iv) $ x1 < x2 \; \&\& \; y1 < y2 $

 

 $=> \left | x1 - x2 \right | + \left | y1 - y2 \right | $ = $ x2 - x1 + y2 - y1 $ $\;=\;$ $(x2 + y2) - (x1 + y1) $

 

항상 양수가 되도록 절댓값을 풀어준 것이기 때문에 네 경우에서의 결과는 모두 양수이다.

 

잘 보면, 결과들은 한 점의 x좌표와 y좌표의 합 또는 차의 '차이'로 나타나는 것을 알 수 있다.

따라서 각 점들의 x와 y의 합과 차를 각각 저장한 후 정렬을 한 다음,

최소 거리를 구한다면 차이가 가장 작은 값, 최대 거리를 구한다면 차이가 가장 큰 값으로 답을 내면 된다. 

 

atcoder.jp/contests/abc178/tasks/abc178_e

E - Dist Max

이 문제는 최대 맨해튼 거리를 구하는 문제이다. 

 

소스 코드를 보면 알 수 있듯이 정렬을 한 뒤에, 첫 번째 원소와 마지막 원소의 차를 이용하여 최대 거리를 구한다. 

만약 최소 거리를 구하라고 하면, 이웃한 두 쌍의 차 중에서 가장 작은 값을 구하면 될 것이다. 

 

시간 복잡도는 정렬하는 시간이 지배하므로 O(nlogn)으로 나온다.

 

#include<iostream>
#include<algorithm>
#include<vector>
 
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
 
using namespace std;
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N; cin >> N;
    vector<pii> p;
    vector<int> plus;
    vector<int> minus;
 
    for (int i = 1; i <= N; i++) {
        int x, y; cin >> x >> y;
        p.push_back({ x, y });
        plus.push_back(x + y);
        minus.push_back(x - y);
    }
    sort(all(plus));
    sort(all(minus));
    cout << max(plus.back() - plus[0], minus.back() - minus[0]);
}

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^