[백준][BOJ9373] 복도 뚫기

1. 문제 : https://www.acmicpc.net/problem/9373

9373번: 복도 뚫기

---

2. 풀이 : Kruskal

---

3. 시간복잡도 : O(N²logN)

---

4. 풀이

그림[1]과 같이 센서가 배치 되어있다고 생각해보자. 문제 조건에의해 왼쪽벽은 x=0인 직선이 되고, 오른쪽벽은 x=20인 직선이 된다.

그림[1]

각 센서들간의 거리를 '두 점 사이의 거리 - 각 센서의 반지름'으로 구해보면 그림[2]와 같다.

그림[2]

이어서, 각 센서들과 벽과의 거리를 구하면 그림[3]과 같다.

그림[3]

거리가 짧은 순서대로 센서 사이를 통과해보며 복도를 통과할 수 있는 원의 최대 반지름을 구해본다.

그림[4]

그림[4]에서처럼 가장 짧은 거리인 -3은 복도를 벗어나는 범위이므로 통과 할 수 없다. 마찬가지로, 그 다음 짧은 거리인 0도 복도와 센서 사이에 지나갈 공간이 없으므로 통과 할 수 없다.

그림[5]

그림[5]와 같이 그 다음 짧은 거리인 1.85는 반지름이 0.925인 원으로 통과가 가능하다.

그림[6]

그림[6]에서 그 다음 짧은 거리인 2.25는 반지름이 1.125인 원으로 통과할 수 있으며, 이 때의 반지름이 문제에서 원하는 답이 된다. 이보다 더 큰 반지름으로는 복도를 통과할 수 없기 때문이다. 각 센서와 벽에 번호를 붙여서 표현을 해보면 그림[7]과 같다.

그림[7]

거리가 짧은 순서대로 -3, 0, 1.85을 연결해보면 그림[8]과 같다.

그림[8]

그림[8]과 같이 연결된 노드들을 하나의 그룹으로 지정한다. 그리고 그 다음 짧은 거리인 2.25를 연결하면 그림[9]와 같이 왼쪽 벽과 오른쪽 벽이 같은 그룹에 속하게됨을 알 수 있다.

그림[9]

즉, Kruskal 알고리즘으로 거리가 짧은 순서로 MST를 생성하는 과정에서, 왼쪽 벽과 오른쪽 벽이 같은 그룹이 되는 시점에 연결되는 거리가 통과할 수 있는 가장 넓은 거리가 된다.

---

5. 코드