Hoon222y

https://www.acmicpc.net/problem/2887 모든 행성이 연결되는 MST를 만드는 문제이다. 하지만 보통 구하느 MST와는 다르게 N의 제한이 10만이기 때문에 모든 간선의 길이를 다 넣어주게 되면 O(N^2)으로 시간초과&메모리 초과 콤비를 맞게 될 것이다. 따라서 간선을 넣어줄 때 필요한 부분만 넣어주는 처리가 필요하다. 핵심은 거리가 Min(x절대값 차이, y절대값 차이, z절대값 차이) 이므로 각각 x,y,z를 기준으로 sort해준 다음 인전한 경우에만 거리를 넣어주는 3N의 시간복잡도를 넣어주게 되면 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484..