백준 9373번 복도 뚫기

문제

승현의 방은 출입 보안이 철저하다. 승현의 방에 들어가려면 많은 센서가 부착된 복도를 지나가야 한다. 센서는 일정 범위에 사람이나 물체가 감지되면 경보를 울린다.

현석은 매우 민첩한 스파이다. 그는 승현의 방에 있는 어떤 기밀문서를 훔쳐와 달라는 의뢰를 받았고, 실행하기에 앞서 현석은 복도 설계도를 입수했다. 현석은 이 설계도를 보고 자신이 직접 들어갈지, 그게 안 된다면 어느 정도의 로봇을 들여보낼 지 결정해야 한다.

현석은 복도를 2차원적으로 해석하기로 했다. 복도의 좌우 벽은 직선으로, 센서와 센서의 범위는 각각 원의 중심과 그 내부로 대응시켰다. 센서는 복도의 벽에 붙어있거나 복도 중간에 위치해 있으며 그 범위는 복도 양 끝 사이에 적절히 위치해 있다. 현석은 또한 센서 사이를 지나가는 물체를 원으로 가정했다.

센서들의 배치도가 주어져 있을 때, 이 원(현석 혹은 로봇)이 센서에 걸리지 않고 복도를 지나갈 수 있게 하기 위한 원의 최대 반지름을 구하자.

예제 입력을 시각화한 것이다.

문제풀이

사용한 알고리즘: Union-Find

(1) 생각

 왼쪽 벽과 오른쪽 벽을 센서와 같은 객체라고 생각했습니다.
 즉 N개의 센서 (index: 0~N) 에 추가로 2개의 센서가 더 있다고 생각했습니다. (총 N+2개)
 왼쪽벽(index: N), 오른쪽벽(index: N+1)

 1. 각 센서(0~N-1 중 하나)들과 왼쪽벽(N) 사이의 지나갈 수 있는 간격
 2. 각 센서(0~N-1 중 하나)들과 오른쪽벽(N+1) 사이의 지나갈 수 있는 간격
 3. 센서들(0~N-1 중 두개) 사이의 지나갈 수 있는 간격
 위의 1, 2, 3 을 한 곳에 저장해줍니다. (간격 만드는 센서 2개, 간격)

 간격이 작은 것부터 탐색하며 매 탐색마다 간격을 만드는 두 센서들을 하나의 component로 union 해주었습니다.
 이때 간격이 작은 것부터 탐색을 하니, 이후 탐색되는 간격은 이번 간격보다 크거나 같습니다.
 따라서 왼쪽 벽과 오른쪽 벽이 하나의 component로 union 되는 탐색순간의 간격이 센서에 걸리지 않고 갈 수 있는 최대 간격(구하고자하는 물체크기) 입니다.

(2) 코드 10~24

 센서 2개와 이들이 만드는 간격을 저장할 struct 하나를 만들어줍니다.

(3) 코드 25~31

 두 센서와 이들의 감시 반경을 생각해 이 두 센서 사이의 지나갈 수 있는 간격을 계산하는 함수를 만들어 줍니다.

(4) 코드 55~72

 '과정(1) 생각' 의 1,2,3 을 구현하는 코드입니다. 모두 벡터에 저장해줍니다.

(5) 코드 73~91

 지나갈 수 있는 간격이 작은 두 센서부터 차례로 union 을 합니다.
 과정(1)에서 설명했듯이, 왼쪽벽(N)과 오른쪽벽(N+1)이 같은 component가 될 때의 지나갈 수 있는 간격이 구하고자 하는 답입니다. (사실 반지름구하라 했으니 나누기 2 해줘야해요)