맨하탄 거리(Manhattan Distance) 개념과 구현해보기

맨하탄 거리(Manhattan Distance) 혹은 맨해튼 거리는 유클리드 거리(Euclidean Distance)와 함께 매우 기초적인 좌표간의 거리를 구하는 방식이다. 이름에서 뉘앙스가 풍기겠지만, 이 맨하탄은 미국 뉴욕시 행정 구역인 그 맨하탄이 맞다. 맨하탄은 인류 최초의 현대 대도시로 불리며, 맨하탄의 상징적인 이미지는 빌딩숲의 이미지이다.

그러다보니 지금은 매우 흔한 모습이지만, 주먹구구식 그리고 계획적이지 않던 기존의 도시와 달리 매우 체계적이고 계획적이다보니 건물들이 사각형으로 촘촘히 체계적으로 이루어진 잘 정돈된 모습으로 알고리즘 이름을 부여받게 되었다.

---

맨하탄 거리는 L1 Distance라고도 불린다. L2 Distance가 유클리드 거리인데 그만큼 유클리드보다 공식이 더 쉽기 때문이기도 하다. 바로 이전 포스팅에서 유클리드 거리가 가장 베이스한 알고리즘이라 하였는데 맨하탄 거리가 나오기 전 유클리드 거리를 먼저 만든 선조들(서양 선조지만 인류의 선조)의 위대함이 느껴진다.

유클리드 거리가 피타고라스 정리로 끝나는 것처럼 맨하탄 거리는 이 이미지 하나로 모든 것이 끝이 난다. 좌측 아래 점과 우측 상단 점을 각각 시작점과 도착점이라 봤을 때, 최단거리는 유클리디안 거리로 구하면 된다. 즉, 초록색은 유클리드 거리를 선으로 그은것과 같다.

그러나 좌표가 아니라 도시라고 생각을 해보자, 도시가 유클리드 거리를 연산하는 것처럼 뻥 뚫려 있을리가 없다. 그렇기 때문에 현실적인 거리를 구해야 하는데 건물이 위 이미지 모양처럼 있다면 우리는 가장 가까운 거리는 대부분 파란색이라 착각할 수 있다. 왜냐하면 최단거리인 초록색과 가장 인접해 있기 때문이다.

하지만, 파란색과 노란색과 붉은색 선들은 모두 총길이가 같다는 함정이 있다. 이것이 바로 맨하탄 거리이다. 맨하탄 거리는 왼쪽 아래의 좌표를 (x1, y1)이라 하고, 우측 상단의 좌표를 (x2, y2)라고 할 때, 맨하탄 좌표의 공식을 적어보면 다음과 같다.

|x₁ - x₂| + |y₁ - y₂|

당황스러울 정도로 짧다. 결국 x값의 차와 y값의 차를 각각 절대값으로 바꾼 후, 합한 값이 바로 맨하탄 거리 공식이다. 유클리디안 거리는 각각의 차이에 제곱을 하였고, 마지막에 루트를 씌운 것에 대비해서 훨씬 간단(맨하탄에서 추가로 들어간거라면 절대값을 넣은 정도)하다.  이 알고리즘을 3차원으로 확장하면 다음과 같다.

|x₁ - x₂| + |y₁ - y₂| + |z₁ - z₂|

결국 맨하탄 거리의 최종 공식은 다음과 같은 모습으로 표현될 수 있을 것이다.

그럼, 이제 이 공식을 토대로 실습을 자바(Java) 언어로 수행해보도록 하자

메소드를 구현한 방식

위 공식을 토대로, 맨하탄 거리를 구하는 메소드를 만들어보고 결과가 맞는지 확인해보자

public static void main(String[] args) {
    double[] a = {-1,2,3};
    double[] b = {4,0,-3};
        
    calcManhattanDist(a,b);
}
    
public static void calcManhattanDist(double[] a, double [] b) {
    double sum = 0;
    for(int i = 0; i < a.length; i++) {
        sum += Math.abs(a[i]-b[i]);
    }
        
    System.out.println("ManhattanDistance Distance:" + sum);
}

ManhattanDistance Distance:13.0

위와 같이 코딩할 경우, a와 b의 맨하탄 거리는 13이라는 값이 나오게 된다. 

Apache Math3를 이용한 방식

Apache Math3 Maven 경로

<!-- https://mvnrepository.com/artifact/org.apache.commons/commons-lang3 -->

<dependency>

  <groupId>org.apache.commons</groupId>

  <artifactId>commons-lang3</artifactId>

  <version>3.9</version>

</dependency>

public static void main(String[] args) {
    double[] a = {-1,2,3};
    double[] b = {4,0,-3};
        
    ManhattanDistance manhattan = new ManhattanDistance();
    System.out.println("ManhattanDistance Distance:" + manhattan.compute(a, b));
}

ManhattanDistance Distance:13.0

참고로 Math3 메소드는 유클리디안 거리 등을 구하는 메소드도 제공하고 있으니 Math3를 이용하는 케이스가 많을 경우 Math3를 임포트하여 연산을 하는 것도 좋겠지만 기본적으로 라이브러리가 무겁기(2MB가 넘는 용량) 때문에 왠만해서는 공식을 메소드로 만들어서 사용하는 것이 좋겠다.

참고자료

https://ko.wikipedia.org/wiki/%EB%A7%A8%ED%95%B4%ED%8A%BC_%EA%B1%B0%EB%A6%AC

연관자료

유클리디안 거리(Euclidean Distance) 개념과 구현해보기