[백준] BOJ 1967 - 트리의 지름

2022-11-16

문제 보기

풀이

트리에서 어떤 두 노드 사이의 경로들 중 가장 긴 경로의 길이를 트리의 지름이라고 한다.

가중치가 있는 트리에서, 트리의 지름을 구하는 문제이다.

DFS를 사용해 풀었고, 가중치가 있기 때문에 가중치에 대한 처리도 해주어야 한다.

인접 리스트를 구현할 때, pair로 가중치도 함께 저장해 두었다.

가중치와 상관없이 리프 노드와 리프 노드 사이의 경로가 가장 길 것이다.

루트 노드에서 DFS탐색해 리프 노드들을 구한 뒤 각각의 리프 노드에서 DFS탐색해주며 가중치 합이 가장 높은 경로의 값을 구해주면 된다.

  • C/C++