2887 행성터널

 

1.접근

N의 범위를 모르고 (1 ≤ N ≤ 100,000) 모든간선을 만드는 N^2으로 풀었다가 시간초과를 받았다.

그래서 NlogN으로 풀려고 정렬을 생각했다.

2.풀이

정점들이 주어진다고 해서 이전문제들 같이 모든 간선을 만들 수 없다. 근데 만들필요도 없다.

터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이라고 했으므로 x,y,z축들의 값을 따로 따로 보면된다.

이 부분이 생각하기 힘들었는데 x,y,z축 좌표들을 각각 정렬해놓고 바로 앞,뒤 값들의 차이로 간선들을 만들고 힙에 넣으면 된다. 이렇게 되면 힙에서 빠져 나오는 값들은 비용의 최소값부터 나올 것이다. x,y,z축을 정렬해줄때 좌표의 값도 같이 넣어주어야 쉽다.

이후 유니온 파인드와 크루스칼 알고리즘을 사용하면 된다.

3.코드

4.배운점

• 처음에 각각봐야된다는 것은 생각했지만 정렬을 하여 각각의 차이를 보면 최소값들일 것이라는 생각을 못했다.
• 10000이 넘을땐 NlogN을 바로 생각해보자.
• 유니온 파인드에서 병합할때는 find된 값들의 부모를 바꾸자.