최소 신장 트리의 복수
최소 신장 트리는 그래프의 모든 vertices를 연결했을 때 edge 가중치의 합이 최소가 되도록 하는 것을 말한다.
그런데 이 문제는 분명 N개의 행성을 N-1개의 터널로 잇는다는 점에서 최소 신장 트리는 맞는데 뭔가 이상하다. 모든 행성끼리 연결되어있는 구조이다.
심지어 행성의 개수는 최대 10만개이다. 벌써 머리가 지끈거린다...
크루스칼? 프림?
내가 예전에 푼 문제는 전부 크루스칼을 사용하였다. 이유는 단지 크루스칼로 푸는게 더 쉬워서기도 했고, 둘 다 상관없었다.
일단 이번 문제에서 노드는 다른 노드와 전부 연결, 즉 fully-connected graph이기 때문에 간선 개수 E는 V(V-1)/2개이다. O(ElogE)인 크루스칼보다는 O(ElogV)인 프림을 쓰는 것이 조금 더 효율적이다. 그러나 log 안에 있기 때문에 2배 차이가 난다는 점에서 드라마틱한 시간 감소 효과를 보기는 어렵다.
피보나치 힙을 쓰면 O(E+logV) 시간 내로 해결할 수 있다고 하는데, 구현이 복잡해서 좀 그렇다-ㅅ-
그냥 익숙한 것을 쓰는 게 맞다고 생각한다.
일단 프림 알고리즘으로 도전해본다.
MLE
메모리 초과가 났다. 사실 당연한게, 한 번에 간선을 전부 고려하면 너무 많다. 중간중간마다 간선 거리를 계산하고, 필요 없는 것은 계산조차 안하는 방향으로 가는 것이 맞다고 판단했다. 안되면 더 고민해보고...
TLE
이번엔 TLE가 떴다(정신 나가겠다). 더 계산할 걸 줄이거나 효율적으로 계산하거나 해야 될 듯 하다.
Solved
문제 접근 자체가 잘못되었다. 모든 간선에 대해서 직접 계산을 진행하면 계산량이 감당하지 못한다. 여기서 pruning의 중점은 x, y, z를 따로 보는 것이다.
그렇다면, x좌표만 사용했을 때 행성을 비교해보자. 일렬로 나열된 행성들은 서로 인접한 행성도 있을 것이고, 멀리 떨어진 행성도 있을 것이다. 여기서, 멀리 떨어진 두 행성 사이에 다른 행성이 존재한다면 그 행성도 잇는 것이 더 효율적이다.
마찬가지로, y와 z좌표만 사용했을 때도 그렇다. 그렇다면 x, y, z좌표 모두 사용한다면 그 결과는 달라질까? 결과는 그렇지 않다. 더 효율적인 경로가 존재해야 된다면 다른 좌표로 그 행성을 연결해야 하는데, 어차피 지나는 경로 상에서는 행성을 잇든 잇지 않든 거리 상의 손해가 나지 않는다. 즉, 더 효율적인 경로는 존재할 수 없다. 이미 가장 효율적인 경로이기 때문이다.
이렇게 접근한다면, 굳이 priority queue를 사용한 프림 알고리즘을 사용할 이유가 없다. x, y, z 전체를 일렬로 나열하고 정렬한 뒤 사이 간격을 행성끼리의 거리로 계산하면 3*행성개수만큼의 터널만 생성되기 때문이다.
Kruskal을 사용할 때가 왔다. union-find 알고리즘을 사용하여 풀면 solved이다.
결론
MST는 O(ElogE) 내로 풀어야 하므로 간선의 개수를 고려하여 문제를 풀어야 한다. 문제에서 간선의 개수는 10만개^2이므로 모든 간선에 대해 계산하려고 달려드는 것보다는, 다른 트릭을 발견해내는 것이 이 문제의 키포인트, 중점이었다.
문제
