algospot 요새 (문제 ID: FORTRESS) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/FORTRESS

algospot.com :: FORTRESS

원모양의 성벽이 있다 각 성벽안에는 또 다른 성벽이 있을 수 있다.

성벽들의 좌표와 반지름이 주어졌을때 가장 성벽을 많이 넘어야 하는 두 지점 간을 이동하기 위해 몇 번이나 성벽을 넘어야 하는지 계산하는 문제다.

 

성벽 안에 성벽이 있을때 바깥에 있는 성벽을 조상노드 안쪽에 있는 성벽을 자손 노드로해서 성벽들의 정보를 트리로 표현할 수 있다.

구현한 트리에서 최장 경로의 길이가 곧 구하고자하는 문제의 답이 된다.

트리의 최장 경로의 길이는 트리의 서브트리가 두개이상 있을경우 서브트리들 중 높이가 가장 큰 두 서브트리의 높이합 +2이다.

트리의 서브트리가 한개 이하일 경우 서브트리의 높이 +1이 최장 경로의 길이가 된다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/21.%20Tree%20traversal/FORTRESS.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2