트리 문제인 것은 알았지만, 첫 번째 시도한 방법은 깊이가 가장 깊은 것과 그 다음 깊은 것을 더해주면 최장 길이가 나오지 않을까 하는 것이었다. 그러나 잎에서 출발해 루트까지 도달하지 않고 잎으로 가는 경우가 있다는 것에서 잘못된 코드를 짰다는 사실을 인지하고 다시 갈아엎었다..
직접적으로 트리 구조를 구현하기 시작했으나 클래스를 또 하나 만들면서 재귀적으로 트리 구조를 구현하다가 포기. 책을 보았다.
[Idea Point]
문제 해결의 핵심은 자식 성벽이 부모 성벽의 바로 밑 자식인지 체크하는 메소드가 필요하다는 것이었다. 자식인지 아닌지 체크하는 메소드를 활용해서 O(n)으로 바로 밑 자식인지를 체크할 수가 있다.
내가 처음에 접근했던대로 좌표, 반지름 등의 배열 여러개와 성벽 인덱스만 가지고도 트리를 구현할 수 있다.
https://algospot.com/judge/problem/read/FORTRESS