[백준 1167 C++] 트리의 지름

트리의 지름 문제 링크 (백준(BOJ) 1167번 문제): https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

문제 설명

백준 1167번 트리의 지름 문제는 가중치가 있는 트리에서 노드 간에 거리가 가장 먼 트리의 지름을 구하는 문제이다. 

문제 풀이 

백준 1167번 트리의 지름 문제는 깊이 우선 탐색(Depth First Search) 혹은 너비 우선 탐색(Breadth First Search) 알고리즘을 사용하여 풀 수 있는 문제이다. 

 

첫 번째 시도 (시간 초과) 

처음 시도한 방법은 노드의 끝을 의미하는 리프 노드에서 다른 리프 노드 간에 거리가 최대인 값을 구하는 방식으로 구현을 하였다. 즉, 각 정점을 다 돌면서 Vector Size가 1 인 노드가 있는 경우, 리프 노드이므로 DFS 알고리즘을 돌려 최대인 값을 도출하는 방식으로 시도하였지만 정점이 100,000개로 입력이 주어져서 시간초과가 발생했다. 

 

두 번째 시도 (통과)

첫 번째 시도에서 각 리프 노드에서 DFS를 돌리는 것은 너무 시간이 오래 걸린다는 사실을 알게 되어, DFS를 최소한으로 돌리면서 트리의 지름을 구하는 방법을 생각하였다.

 

[핵심 아이디어]

그 결과 특정 노드 X 에서 DFS를 시행한 후, 특정 X에서 거리가 가장 먼 노드가 트리의 지름을 만드는 2개의 노드 중 하나라는 사실을 알게 되었다. 이후, 위 과정을 거쳐 나온 특정 X에서 거리가 가장 먼 노드에서 다시 DFS를 시행하게 되면, 트리의 지름 값을 얻을 수 있게 된다는 것이었다. 

 

그리하여, 총 2번의 DFS를 통해 지름의 길이를 알 수 있게 되는 것이다. 

이를 코드로 나타내면, 아래와 같이 나타낼 수 있다.