백준 2887번 행성 터널

사용한 알고리즘: MST(최소 스패닝 트리)

​

핵심은 x, y, z축 별로 생각하는 것이였습니다.

각 행성들을 최소 비용으로 연결하여 하나의 컴포넌트를 만드는 것이 목적입니다.

이를 생각하여 x축을 생각해보면,

각 행성들의 x 좌표만을 정렬 해서, A1.x, A2.x, A3.x, ... 와 같이 정렬 됐다고 합시다.

이때 각 행성들은 바로 다음 행성과 연결 될 수 밖에 없습니다. ( 최소 비용을 구하는 것이기 때문)

예를 들어, A1.x 는 A2.x 와 연결 될 수 밖에 없습니다. 즉 A1.x 는 A3.x, A4.x, ... 들과 연결될 수 없습니다.

따라서 이를 생각하여 x, y, z 축 기준으로 각각 정렬하여,

각 이웃한 행성들을 연결하는 비용들을 구해서, 한데 모았습니다.

​

이후 이 x,y,z축 비용들을 한데 모아놓은 벡터를 정렬하여,

하나의 컴포넌트를 만드는 최소 비용을 구했습니다.

이때 A1, A2 행성이 연결해야하는지 확인하는데에, 같은 컴포넌트인지 union-find를 이용했습니다.

이후 N-1번 만큼 연결이 되면, N개의 행성들은 모두 연결됐으므로 연결하는 과정을 끝내고,

답을 도출했습니다.

​