211111 목 Algorithms TIL

행성 터널

• 문제
• 코드
• 동빈북 ch18 기타알고리즘 풀이

내 풀이

• 단순하게 크루스칼 알고리즘을 사용해서 풀었더니 메모리 초과가 나왔다.

동빈북풀이

여기서 핵심은 각 축을 중심으로 n-1개의 길만 고려하면 된다는 것이다. 예를 들어 행성이 4개가 있을 때 어쨌든 x축, y축, z축 각각으로 정렬하면 이 일렬로 정렬되게 된다. 그럴 떄 아래 그림처럼 3개만 고려하면 된다. 다른 길은 이 가장 작은 3개의 길을 합친 것이기 때문에 고려할 필요가 없다.
이 한 축(x축)으로도 얘네는 하나의 루트를 완성할 수 있다 (== 최소 신장 트리 완성)