맨해튼 거리

유클리드 거리를 이용해 두 포인트 사이의 거리를 재는 것이 모든 문제를 해결하는 것은 아닙니다. 예를 들어, 지도상의 두 포인트 사이를 자가용이나 택시로 이동하는 거리는 유클리드 거리보다 더 깁니다. 이 경우에는 두 포인트 사이의 가장 긴 경로를 표현하는 맨해튼(Manhattan) 거리를 사용하는 것이 좋습니다. 다음은 맨해튼 거리와 유클리드 거리를 비교한 그림입니다.

▲ 그림 6-6 맨해튼 거리와 유클리드 거리 비교

맨해튼 거리는 항상 유클리드 거리보다 크거나 같다는 점을 기억하세요.