Algorithm: Kruskal Algorithm & Binary Search

크루스칼 알고리즘이란 최소 신장 트리를 찾는 그래프 알고리즘 중 하나이다.

이때, 그래프는 무방향이다.

 

최소 신장트리(Minimum Spanning Tree: MST)란 모든 정점을 포함하면서 그래프의 모든 간선의 가중치 합이 최소인 트리를 의미.

    --> 사이클 없이 모든 노드가 연결되어야 한다.

 

동작원리

    --> 그래프의 모든 간선을 오름차순 정렬

    --> 가중치가 가장 작은 간선 선택

    --> 이 간선이 최소 신장 트리에 이미 포함되어 있는지 확인

    --> 포함되어 있지 않다면 해당 간선을 MST에 추가

 

문제 1)

풀이 1:

    --> 각 질의마다 크루스컬 알고리즘을 돌리며 연결 되는 순간 에지의 가중치 값이 질의의 답 c

    --> 이때 크루스컬 알고리즘에 O(|E|log|V|) 시간, 총 Q의 질의 가 있으므로 O(Q|E| log |V|) 의 시간

 

풀이 2:

    --> c 값을 이분 탐색으로 찾는다.

    --> lo = 0, hi = 에지의 가중치중 최대값.

    --> 이때, c의 값은 (lo, hi]에 있는것이 자명하다

    --> mid = (lo + hi)/2 

    --> w(e) <= mid 인 에지만드로 u 와 v를 연결할 수 있는지 확인

            --> 연결할 수 있다면 c는 (lo, mid] 내에, 연결할 수 없다면 c는 (mid, high]에 있다.

    --> 하지만 결국 시간복잡도는 풀이 1 과 같다..

더 빠른 풀이:

    --> idea: Q 개의 질의가 있을 때, 질의의 같은 단계를 한번에 처리하자.

    --> 4개의 질의가 있다고 하자 (Q1,Q2,Q3,Q4)

    --> 처음에 4개의 질의의 lo, hi, mid 값이 모두 같다. 

    --> 크루스컬 알고리즘을 한번 돌려서 가중치가 mid 인 에지까지 읽었을 때 종료

    --> 두번째에서 Q1,Q2는 mid 보다 커야 하고 Q3,Q4는 mid 보다 작아야 한다 가정.

    --> 세번째에서 mid 값이 같은 질의끼리 모은 뒤, 각 집합에 대해 크루스컬 알고리즘 진행

    --> 총 시간 복잡도는 O(Q+|E|) log |E|)

 

문제 2)

 

풀이:

    --> 수 i 가 쓰인 노드를 A, B, C 라고 할 때, A, B, C가 모두 연결되는 최초 시점을 묻는 것이다.

    --> 노드 A 와 B 가 연결되어 있고, 노드 A 와 C 가 연결되어 있다면 노드 B 와 C 또한 연결되어 있다.

 

    --> mid 값을 이용하여 A와 B, A 와 C 를 연결할 수 있는지 검사( 1에서 mid 번 까지의 에지만응 이용)

    --> 두가지 케이스 모두 연결이 가능하다면 그 때의 mid 값은 ABC를 연결할 수 있는 최소한의 i 값

    --> 한가지 케이스라도 연결할 수 없는 경우, mid 값 이후의 범위에서 다시 검사 수행

    --> 각 노드 쌍에 대해 최대 한번만 질문하기 때문에 질문의 개수는 노드의 수보다 많지 않다.