홍라이프 계산기맨해튼 거리 계산기 쉽게 이해하기 — 개념과 원리
이 계산기는 2차원이나 3차원의 두 점 사이 맨해튼 거리(택시 거리, 블록 거리), 곧 격자선을 따라서만 움직일 때의 거리를 구합니다. 직선 거리와 비교하고, 가장 짧은 격자 경로가 몇 가지인지도 셉니다. 도시 길찾기 퍼즐, 격자 게임, 창고 배치, 데이터 과학에 쓸 수 있습니다. z좌표를 0으로 두면 평면 문제가 됩니다.
계산 방법
맨해튼 거리 = |x₁ − x₂| + |y₁ − y₂| (3차원이면 + |z₁ − z₂|)
직선(유클리드) 거리 = √(Δx² + Δy² + Δz²)
2차원 정수 격자에서 가장 짧은 경로의 수 = C(|Δx| + |Δy|, |Δx|)
원리
바둑판 모양의 도로에서는 블록을 대각선으로 가로지를 수 없으므로, 동서 방향 차이와 남북 방향 차이를 순서와 상관없이 모두 가야 합니다. 그래서 거리는 절댓값 차이의 합입니다. 가장 짧은 경로는 모두 동쪽 걸음과 북쪽 걸음의 수가 같고 순서만 다르므로, 경로의 수는 어느 걸음을 동쪽으로 할지 고르는 방법의 수입니다. 이 예라면 전체 14걸음 가운데 동쪽으로 갈 6걸음의 자리를 고르는 조합입니다. 직선 거리는 절대 더 길지 않으며, 두 거리는 한 좌표만 다를 때만 같습니다.
예제 풀이
기본값: A = (1, 2, 0), B = (7, 10, 0).
- |Δx| = |1 − 7| = 6, |Δy| = |2 − 10| = 8, |Δz| = 0입니다.
- 맨해튼 거리 = 6 + 8 + 0 = 14입니다.
- 직선 거리 = √(36 + 64) = 10입니다.
- 맨해튼 ÷ 직선 = 1.4입니다.
- 가장 짧은 격자 경로 = C(14, 6) = 3,003가지입니다.
| 점 B: y₂ | 맨해튼 거리 |
|---|---|
| 2.5 | 6.5 |
| 5 | 9 |
| 7.5 | 11.5 |
| 10 | 14 |
| 12.5 | 16.5 |
| 15 | 19 |
| 20 | 24 |
결과 해석
비율 1.4는 이 경우 격자를 따라 가는 길이 직선보다 40% 길다는 뜻입니다. 2차원에서 이 비율은 가로와 세로 걸음이 같은 대각선 이동일 때 √2 ≈ 1.41로 가장 큽니다. 데이터 과학에서는 맨해튼 거리가 큰 차이 하나에 유클리드 거리보다 덜 휘둘리는 특징이 있어, 이상값이 섞인 자료를 비교할 때 쓰이기도 합니다. 길찾기 게임이나 로봇 경로 계산에서도 대각선 이동이 없을 때 기본 거리로 씁니다.
흔한 실수
- 절댓값을 빼먹어 차이가 서로 지워지는 경우
- 절댓값 차이 대신 제곱을 더하는 경우
- 걸음이 격자 단위가 아닌데 경로 수를 세는 경우
- 맨해튼 거리가 직선보다 짧을 것이라 기대하는 경우
- 3차원 문제에서 z 차이를 빠뜨리는 경우
자주 묻는 질문
(1, 2)와 (7, 10)의 맨해튼 거리는?
14입니다.
왜 택시 거리라고 부르나요?
바둑판 도로에서 택시가 실제로 달리는 거리이기 때문입니다.
가장 짧은 경로는 몇 가지인가요?
C(Δx + Δy, Δx)이며, 여기서는 C(14, 6) = 3,003가지입니다.
체스판의 킹 이동 거리와는 다른가요?
다릅니다. 대각선 이동이 허용되면 max(|Δx|, |Δy|)인 체비쇼프 거리가 됩니다.
출처: E. W. Weisstein, "Taxicab Metric", Wolfram MathWorld