링크

문제 요약

$i$ 번 정점에 정수 $A_i$ 가 적혀있다. $i$ 번 정점과 $j$ 번 정점을 잇는 간선의 가중치는 $A_i \oplus{} A_j$ 일 때, 주어진 그래프의 MST를 구하여라.

관찰

간선의 가중치가 0인 경우를 생각해보면, 이 경우는 $A_i$ 값이 서로 같은 정점들에 대하여 가중치가 0임을 알 수 있다. 이러한 정점들을 일렬로 연결하면, 해당 정점끼리 MST를 이룸이 자명하고 또한 비용의 합 역시 0이다. 실제 MST를 구하는 것이 목표가 아닌 비용만 구하면 되므로, unique 한 $A_i$에 대하여만 문제를 해결해도 됨을 알 수 있다.

이후에 가장 먼저 해볼 수 있는 생각은 기존에 존재하는 MST 알고리즘을 응용해 보는 것이다. 크루스칼 알고리즘을 생각해보면, 크루스칼 알고리즘은 간선의 가중치를 작은 것부터 보면서 2개의 서로 다른 2개의 MST를 1개의 새로운 MST로 합치는 과정을 반복하게 된다. 이 아이디어를 그대로 차용하도록하자. 핵심은 이미 만들어진 2개의 MST $T_1$ 과 $T_2$ 를 최소한의 비용으로 연결하는 것이다.

풀이

이를 구하기 위해서는 $T_1$에 속할 정점과 $T_2$ 에 속할 정점을 나눠야 한다. 어떤 비트 $2^x$ 가 켜진 그룹과 꺼진 그룹으로 $T_1$ 과 $T_2$ 를 나눈다고 생각해보자. 이렇게 할때가 최적의 분할임은 귀류법을 통해 증명이 가능하다.

Proof )
만약 이렇게 나누지 않는 최적의 해가 존재한다고 가정을 하자. 해당 분할을 각각 $T’_1$ 과 $T’_2$ 라고 하면, 각각의 트리 $T’_1$ 과 $T’_2$ 의 내부에서 $2^x$ 비트가 켜지는 경우가 반드시 존재하게 된다. 반면에 앞서 언급한 방식은 $2^x$ 비트가 켜지는 경우가 1개만 존재하므로, 귀류법에 의해 앞서 말한 분할이 최적임을 알 수 있다.

따라서 이 과정을 최상위 비트부터 순서대로 재귀적으로 분할 정복하면 된다. 이때, 두 그룹에서 반대편 그룹으로 간선을 이을 때 최소 비용을 찾는 과정은 Trie를 이용하면 된다. Trie에 반대편 숫자들을 기록하고, 각각의 숫자에 대하여 가장 xor 값이 작은 경우를 그리디하게 구하면 된다. 이때 신경써야 할 부분은 $T_1$ 과 $T_2$ 중 더 크기가 작은 그룹에서 검색을 해야한다는 것이다. 이렇게 할 경우 Trie 에서 검색 횟수가 Small to Large Trick에 의하여 $O(N\log{N})$ 이 됨을 알 수 있다.

전체 풀이에 걸리는 시간을 정리하면 다음과 같다.

주어진 숫자를 unique하게 만드는 과정이 $O(N\log{N})$
각 숫자를 Trie에 저장하는 과정이 $O(30N)$
분할 정복 중 정점 그룹을 $T_1$ 과 $T_2$ 로 분할하는 시간이 $O(30N)$
분할 정복 중 두 그룹을 combine 하는데 드는 시간은 Small to Large Trick 에 의해 $O(30N\log{N})$

따라서 전체 시간 복잡도 $O(30N\log{N})$ 에 문제가 해결된다. 물론 이 경우 상수 30은 Trie 검색에 드는 상수로 구현에 따라 다를 수 있다. 실제로 본인이 작성한 코드도 재귀의 깊이가 깊어질 수록 Trie의 시작 지점도 함께 움직이는 형태로 구현하여 상수를 줄였다.