pts라는 배열에 여러 개의 점이 주어져 있다고 가정해 봅시다. 그리고 우리의 현재 위치를 나타내는 또 다른 점 (x, y)도 함께 주어집니다. 여기서 '유효한 점'이란 현재 위치와 x좌표 또는 y좌표 중 하나라도 같은 점을 의미합니다. 우리가 구해야 하는 값은 현재 위치에서 맨해튼 거리(Manhattan Distance)가 가장 짧은 유효한 점의 인덱스입니다. 만약 조건을 만족하는 점이 두 개 이상이라면, 그중 인덱스가 가장 작은 점을 반환하면 됩니다.
참고로 두 점 (a, b)와 (p, q) 사이의 맨해튼 거리는 다음과 같이 계산됩니다.
|a − p| + |b − q|
예를 들어, 입력이 다음과 같다고 해봅시다.
pts = [(1,2), (3,1), (3,4), (2,3), (4,4)], pt = (2,4)
이 경우 출력은 2가 됩니다. (3,4)와 (2,3) 두 점 모두 현재 위치에서 맨해튼 거리가 같지만, (3,4)의 인덱스가 더 작기 때문입니다.
문제 해결 접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 현재 위치 좌표를 추출합니다: x, y := pt
- 결과 인덱스를 저장할 변수를 초기화합니다: idx := -1
- 최소 거리를 저장할 변수를 무한대로 초기화합니다: smallest := ∞
- pts 배열의 각 점 p에 대해 반복합니다:
- p의 x좌표(p[0])가 x와 같거나 y좌표(p[1])가 y와 같은지 확인합니다.
- 조건을 만족하면 맨해튼 거리를 계산합니다: dist := |x − p[0]| + |y − p[1]|
- dist가 smallest보다 작으면 idx를 해당 점의 인덱스로, smallest를 dist로 갱신합니다.
- dist가 smallest와 같으면, 현재 점의 인덱스가 기존 idx보다 작을 때만 idx와 smallest를 갱신합니다.
- 반복이 끝나면 idx를 반환합니다.
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드
def solve(pts, pt):
x, y = pt
idx = -1
smallest = float("inf")
for p in pts:
if p[0] == x or p[1] == y:
dist = abs(x - p[0]) + abs(y - p[1])
if dist < smallest:
idx = pts.index(p)
smallest = dist
elif dist == smallest:
if pts.index(p) < idx:
idx = pts.index(p)
smallest = dist
return idx
pts = [(1,2),(3,1),(3,4),(2,3),(4,4)]
pt = (2,4)
print(solve(pts, pt))입력
[(1,2),(3,1),(3,4),(2,3),(4,4)], (2,4)
출력
2
정리
이 알고리즘은 모든 점을 한 번씩 순회하며 조건을 검사하므로 시간 복잡도는 O(n)입니다. 유효한 점들 중 맨해튼 거리가 가장 짧은 점을 찾되, 거리가 같은 경우에는 더 작은 인덱스를 우선 선택하는 것이 핵심 포인트입니다. 이러한 방식은 지도상에서 같은 행 또는 같은 열에 있는 가장 가까운 목적지를 찾는 등 실생활의 다양한 경로 탐색 문제에 응용할 수 있습니다.