◼︎ 맨해튼 거리

맨해튼 거리(manhattan distance)는 사각형 격자로 된 지도에서 출발점부터 도착점까지 가로지르지 않고 갈 수 있는 최단 거리를 구하는 공식입니다.

두 점이 도로 정비가 잘된 어떤 도시의 두 장소를 의미한다고 할 때, 한 장소에서 다른 장소로 이동하는 최단 거리는 대각선으로 가로질러 가는 것입니다(유클리드 거리). 하지만 도시에 있는 많은 건물 때문에 가로질러 갈 수 없고 건물들을 피해 목적지를 찾아야 합니다. 가로질러 가는 것이 불가능하다면 그림 10-50과 같은 다양한 방법이 존재할 것입니다. 일반적으로는 ②, ③이 ①보다 빠르다고 생각하겠지만 ①, ②, ③ 모두 길이가 동일합니다(실제로 블록의 면 수를 세어 보면 동일하다는 것을 알 수 있습니다). ①, ②, ③ 길이가 모두 동일하기 때문에 계산의 편리성을 위해 ①의 길이를 이용하여 거리를 계산하게 되며, 계산 방법은 수식 10.19와 같습니다.

그림 10-50 | 맨해튼 거리