알고스팟 요새 FORTRESS

두 원은 만나지 않으면서 겹치치 않는다는 조건이 있다

결국 1. 두 원은 서로 떨어져 있거나 2. 하나의 원이 다른 하나의 원 안에 있거나 둘 중에 하나다

 

원들이 모두 계층적 구조를 가지고 있기 때문에, 트리로 구성할 수 있다. 이전에 서로 원들을 모두 비교하면서 자신의 부모를 찾는다. 조건을 만족하면서 반지름이 작은 부모인 바로 부모노드만을 저장한다. 그 정보를 가지고 트리를 구성하게 된다

 

그리고 최장 거리는 리프노드와 리프노드 혹은 리프노드와 루트와의 거리이므로 bfs를 돌려서 그 거리를 구할 수 있게 된다

 

문제: https://algospot.com/judge/problem/read/FORTRESS

깃허브주소: https://github.com/surinoel/boj/blob/master/FORTRESS.cpp