image.png

문제 파악

원형으로된 요새의 벽을 가장 많이 통과 하는 경우를 구하는 문제이다. 요새의 벽 끼리 겹치는 경우는 없기 때문에 요새가 겹치는 지를 파악하는 아이디어는 쉽게 생각났으나 트리 자료 구조를 표현하는 방식에서 시간이 너무 오래 걸려 포기했다. 가장 많이 겹치는 구간을 구하는 방법은 트리 구조로 된 모습에서 가장 긴 리프에서 리프 까지의 경로 또는 리프에서 루트 까지의 경로를 선택하면 된다.

문제 풀이

트리 구조체는 자식 노드에 대한 포인트만 갖는다. 재귀적으로 트리의 높이를 구하는데, 각 노드의 높이는 리프일 경우 0, 리프가 아닐 경우 서브 트리 별로 재귀적으로 높이를 구하고 가장 긴 경로는 서브 트리 중 가장 높이가 큰 두 값을 더하고 루트를 방문하는 경로인 2를 더해줘서 구한다.

요새 포함 구조

처음 생각한 방식은 원의 중심과 반지름만을 이용해 y값과 x값의 최대치, 최소치만을 이용해 구할 수 있다고 생각했지만 크기 차이가 큰 두 원이 있는 경우 이 범위 안에 속하더라도 원의 대각선 경계를 넘어서는 부분에서 포함 관계가 아닐 수 있다는 걸 알게 되었다. 따라서 수학적 정의대로 원의 중심 사이의 거리와 반지름을 이용해 포함 구조를 결정하는 것이 좋다.

코드 해석

추가 학습 필요