====== 복도 뚫기 ======

===== 풀이 =====
  * 왼쪽 벽에서 임의의 갯수의 센서들을 거쳐서 오른쪽 벽으로 연결되는 경로를 생각하자. 이것은 왼쪽벽에서 오른쪽벽까지 연결되어 복도의 통행을 막는 장애물벽같은 느낌으로 생각할수 있다. 각 센서의 커버범위가 기둥을 이루고, 커버 못하는 구간 (=센서간 간격)이 통과 가능한 부분이라고 생각하면, 이 장애물벽을 통과하기 위해서는 물체의 지름이 가장 큰 센서간 간격보다는 작아야 한다.
  * 이 조건을 모든 가능한 왼쪽벽->오른쪽벽 경로에 대해서 만족해야 한다. 왼쪽벽->오른쪽벽 경로중에서, 센서간 간격의 최대값이 가장 작은 경로를 찾게 되면, 그때의 센서간 간격이 통과 가능한 물체의 지름과 동일하다.
  * 이제, 문제를 그래프로 모델링하자. 각 센서와 왼쪽벽, 오른쪽 벽이 노드가 되고, 엣지들의 가중치는 두 노드 사이의 간격으로 주면 된다. 벽과 센서 사이의 간격은 {x좌표의 거리 - 센서의 반지름}이 되고, 센서와 센서사이의 간격은 {두 센서 사이의 유클리디안 거리 - 반지름들의 합} 이 된다. 이렇게 만든 그래프에서 왼쪽벽부터 오른쪽 벽까지의 [[ps:최소 신장 트리#bottleneck shortest path problem]] 을 구하는 문제가 된다. 이 것은 링크에서 설명했듯이, O(E)알고리즘도 있긴 하지만, 그냥 [[ps:최소 신장 트리]]를 이용해서 구하는 것이 무난하다. 
  * 최소신장트리 알고리즘을 돌려서 트리를 추출한 뒤에 거기에서 다시 경로에 해당하는 엣지들만 남기는 작업을 하는 방법도 있지만, 코드가 더 길어지는 느낌이라서, 그냥 최소신장트리 알고리즘을 조금 변형해서, 트리를 만들다가 경로가 연결되면 중단하는 식으로 사용했다. 그래프가 dense하기 때문에 크루스칼 알고리즘 대신 프림 알고리즘을 이용해서 처리했다. 시간복잡도는 O(V^2)
 
===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 9373. 복도 뚫기".

- Problem link: https://www.acmicpc.net/problem/9373
- Solution link: http://www.teferi.net/ps/problems/boj/9373
"""

import sys
import math


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        w = int(sys.stdin.readline())
        n = int(sys.stdin.readline())
        censors = [
            [int(x) for x in sys.stdin.readline().split()] for _ in range(n)
        ]

        if n == 0:
            print(w / 2)
            continue

        dists = {i: max(0, x - r) for i, (x, y, r) in enumerate(censors)}
        closest_node = min(range(n), key=dists.__getitem__)
        dist_to_right = w
        answer = dists[closest_node] / 2
        while closest_node is not None:
            u_x, u_y, u_r = censors[closest_node]
            del dists[closest_node]
            dist_to_right = min(dist_to_right, max(0, w - u_x - u_r))
            closest_node, min_dist = None, dist_to_right
            for v, dist_v in dists.items():
                v_x, v_y, v_r = censors[v]
                d = max(0, math.dist((u_x, u_y), (v_x, v_y)) - (u_r + v_r))
                if d < dist_v:
                    dist_v = dists[v] = d
                if dist_v < min_dist:
                    closest_node, min_dist = v, dist_v
            answer = max(answer, min_dist / 2)

        print(answer if answer > 0 else '0')


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_2}}