트리의 지름 구하기 (알고리즘)

Photo by Fabrice Villard on Unsplash / 난 눈이 좋다.

백준 1967번 트리의 지름 문제를 풀기 위해 공부한 내용을 기록한다.

우선 문제를 보자.

문제에서 알 수 있드시,

1. 우리는 트리에서 가장 긴 엣지를 가진 정점을 찾아야 한다. 이 정점은 dfs를 통해 찾을 수 있다.
2. 위 dfs에서 찾은 가장 긴 엣지를 가진 정점에서, 반대쪽으로 가장 긴 엣지를 가진 정점을 찾아서 매 재귀마다 엣지의 길이를 더하면 트리의 지름을 구할 수 있다.

총 dfs가 2번 필요하다. 위 과정을 코드로 보면 아래와 같다.

끝!