[BOJ] 행성 터널_2887

 

위 문제는 N개 노드의 간선이 될 수 있는 모든 경우의 수를 판단해 준 후, 크루스칼 알고리즘을 활용하려 했다.

하지만 N의 갯수가 최대 10만이기 떄문에 N(N-1)과 같은 방식으론 해결할 수 없다.

 

이를 해결한 풀이는 다음과 같다.

x, y, z를 각각 나눠서 생각해본다.

x=[]에는 x값을 정렬한 후, 거리를 계산한 값만 추가한다.

y, z, 도 방금 한 x와 똑같이 수행한다.

 

그 후 data배열에 다 추가한다. 그럼 완벽히 최소 값부터 정렬된 것은 아니겠지만, 그래도 x, y, z의 각각 자신이 갖고 있는 최소값을 추가해주는 상황이다.