맨해튼 거리(Manhattan Distance)

코딩테스트를 하면서 프로그래밍언어나 SQL 구현 문제로 가끔씩 출제가 되는 거리 측정 방법에 대해 알아보자.

맨허튼 거리(Manhattan Distance) 는 2차원 평면 공간에서 두 점 p와 q 사이의 거리를 측정하는 방법 중 하나로, 두 점 사이의 수평 및 수직 이동 거리의 합으로 정의된다.

즉, 맨허튼 거리가 (p1,p2) 와(q1,q2) 사이면
맨허튼 거리 = ∣p1−q1∣+∣p2−q2∣ 이다.

여기서 |p| 또는 |q| 는 절대값을 나타내며, 수평방향(p) 수직방향(p)의 거리를 모두 더한 값이다.

맨허튼 거리는 유클리드 거리와는 다르게 대각선 방향의 이동을 고려하지 않는다. 오로지 수평 및 수직 방향의 이동만을 고려한다. 이로 인해 실제 도로 네트워크나 격자 형태의 구조에서 두 지점간의 이동 거리를 좀 더 정확하게 나타낼 수 있다.

맨허튼 거리(Manhattan Distance)는 다음과 같은 상황에서 유용하게 사용 될 수 있으므로 이해만 하고 넘어가자.

1. 물류

택배 회사나 배송 업체에서 배송 경로를 최적화 할때 사용 된다.

2. 도시 계획

도시의 도로 네트워크 및 고통 흐름 분석 및 도시 발전 방향을 계산할때 사용 된다.

3. 비전 및 머신러닝

객체 간의 거리를 측정하거나 이미지 처리에서 특징을 추출하는데 사용된다.

4. 게임 개발

게임내 캐릭터나 NPC의 이동 경로를 계산하거나 충돌 감지에 사용 된다.