BOJ 9373 - 복도 뚫기

문제

링크: https://www.acmicpc.net/problem/9373

복도에 센서들이 있고 센서들을 피해 복도를 통과할 수 있는 가장 큰 원의 반지름을 구하는 문제이다.

복도의 너비가 주어지고, 각 센서들의 좌표 x, y와 반지름 r이 주어진다.

처음에는 센서와 센서 사이에 존재할 수 있는 원들로 어떻게 MST를 잘 만들면 되지 않을까했는데, 가장 큰 원의 반지름을 구하기가 힘들었다. 하루 정도 계속 틀리고 고민하고를 반복하다 솔루션을 찾아봤다.

솔루션을 보자마자 와 이게 뭐지 싶었다. 이렇게 풀 수도 있구나 신기했다.

풀이

최소 신장 트리 문제는 맞았고 원과 원 사이의 끼인 원으로 어떻게 하는 것도 맞았다. 근데 최종형태가 이런 식이었다.

양쪽 벽을 큰 집합이라고 생각하고 두 집합이 연결될 때까지 MST를 만든다. 크루스칼 알고리즘으로 해결하면 간단하다.

센서(원)의 개수가 \(n \leq 1,000\) 이라서 모든 원들 사이의 작은 원의 거리를 간선으로 연결해도 무방하다. (\(N\)이 크면 어떡할까? 평방분할 같은거로 좌표압축해서 빠르게 찾아야 하나...? 고민해봐야겠다)

왼쪽 벽 집합과 오른쪽 벽 집합이 같아졌다는 것은 간선이 서로 연결되었다는 의미이다. 그리고 이것은 다시 말해, 복도를 지날 수 있는 가장 큰 원을 찾았다는 뜻이다. 어떻게 이런 생각을 하는 걸까..