(x, y) 형식의 일부 포인트가 있는 포인트라는 배열이 있다고 가정합니다. 이제 두 점 (xi, yi)과 (xj, yj)를 연결하는 비용은 두 점 사이의 맨해튼 거리이며 공식은 |xi - xj| + |이 - yj|. 모든 포인트를 연결하기 위한 최소 비용을 찾아야 합니다.
따라서 입력이 points =[(0,0),(3,3),(2,10),(6,3),(8,0)]과 같으면 출력은 22가 됩니다. 피>
따라서 총 거리는 (6+5+3+8) =22입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- points_set :=범위 0에서 포인트 크기 - 1까지의 숫자를 포함하는 새로운 세트
- heap :=(0, 0) 쌍으로 힙 만들기
- visited_node :=새로운 세트
- total_distance :=0
- 힙이 비어 있지 않고 Visited_node의 크기 <포인트의 크기, do
- (distance, current_index) :=힙에서 요소 삭제
- 현재_색인이 방문된 노드에 없으면
- 현재_색인을 방문된 노드에 삽입
- points_set에서 current_index 삭제
- total_distance :=total_distance + 거리
- (x0, y0) :=포인트[현재_색인]
- points_set의 각 next_index에 대해 다음을 수행합니다.
- (x1, y1) :=포인트[next_index]
- 힙에 (|x0 - x1| + |y0 - y1| , next_index) 삽입
- 반환 total_distance
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
import heapq def solve(points): points_set = set(range(len(points))) heap = [(0, 0)] visited_node = set() total_distance = 0 while heap and len(visited_node) < len(points): distance, current_index = heapq.heappop(heap) if current_index not in visited_node: visited_node.add(current_index) points_set.discard(current_index) total_distance += distance x0, y0 = points[current_index] for next_index in points_set: x1, y1 = points[next_index] heapq.heappush(heap, (abs(x0 - x1) + abs(y0 - y1), next_index)) return total_distance points = [(0,0),(3,3),(2,10),(6,3),(8,0)] print(solve(points))
입력
[(0,0),(3,3),(2,10),(6,3),(8,0)]
출력
22