멘헤튼 거리

격자에서 중요하게 사용되는 개념

오직 상, 하, 좌, 우로만 이동할 수 있을 때의 최단 거리

두 점 (x1, y1)과 (x2, y2) 사이의 맨해튼 거리는 다음과 같이 간단하게 계산할 수 있습니다.

맨해튼 거리 = |x1 - x2| + |y1 - y2|

(x좌표의 차이의 절댓값 + y좌표의 차이의 절댓값)

1. 영향 범위 계산: 특정 지점으로부터 맨해튼 거리가 k 이하인 모든 지점들의 집합은 마름모 모양을 이룹니다. 바로 이전에 질문하셨던 "황금 채굴하기" 문제에서 마름모 모양의 채굴 범위가 맨해튼 거리의 대표적인 활용 예시입니다.

   • 맨해튼 거리 1: + 모양 (5칸)

   • 맨해튼 거리 2: 중심을 포함한 13칸짜리 마름모

   • 맨해튼 거리 k: kk + (k+1)(k+1)개의 칸으로 이루어진 마름모

유클리드 거리(Euclidean Distance)와의 비교

• 유클리드 거리: 두 점 사이의 직선 거리입니다. sqrt((x1-x2)² + (y1-y2)²).

• 맨해튼 거리: 두 점 사이의 격자 경로 거리입니다. |x1-x2| + |y1-y2|