남극기지

문제: 남극기지 / 그래프 or 이진탐색

모든 노드가 전파를 받을 수 있어야 하고 전파의 출력은 최소화 해야한다.

이 문제를 해결하는데 두 가지 방법을 사용할 수 있다. 

1. parametric search 

parametric search는 어떤 알고리즘으로 해를 바로 구해내는 것이 아니고, 임의의 값을 던지고 맞는지 확인해가며 해를 구하는 방법이다. 앞에서 언급한 임의의 값을 정하는 과정에 이진탐색이 사용될 수 있다. 

이 방법을 이용한 알고리즘은 다음과 같다.

1. 초기 값으로 해의 최소값과 최대값을 이진탐색의 low, high 값으로 각각 지정한다. 

2. mid((low+high)/2)값이 해가 될 수 있는지 검사해본다. 이말의 의미는 전파의 출력이 mid값인 경우 모든 노드들이 연락을 주고 받을 수 있는지 여부를 가려내야 한다는 것이다. 

3. mid값으로 해결 된다면 high값을 mid 값으로 만들어 범위를 좁혀가면서 해를 구해나간다. 반대의 경우 low값에 mid값을 넣어준다. 2번부터 반복.

위 과정을 반복하면 된다. 나는 mid값을 검증하는 과정에 BFS(Breadth First Search)를 사용했다. 

이 경우 시간복잡도는 이다. D(Distance)는 해의 범위에 해당한다. (여기서는 전파의 출력범위)

코드: https://github.com/xgate/algospot/blob/master/GRAPH/ARCTIC1.cpp

2. 최소비용 신장트리(MST: Minimum Spanning Tree)를 이용

두 번째 방법은 MST를 만들어가는 과정을 이용하는 것이다. 

MST를 만들어가는 알고리즘 중 prim 알고리즘이 있는데 이 알고리즘의 동작과정은 다음과 같다.

1. 출발점 노드를 노드집합(S)에 넣는다. 남은 노드들의 집합은 X라고 하자.

2. S에 있는 노드와 연결된 X에 속한 노드 중 거리가 가장 짧은 노드를 S에 포함시킨다. X에 노드가 없을 때까지 반복.

2번 과정에서 결정된 거리값 중 최대 값을 골라내면 그 값이 바로 해가 된다. 시간복잡도는 

코드: https://github.com/xgate/algospot/blob/master/GRAPH/ARCTIC2.cpp