[BOJ]1167번: 트리의 지름

www.acmicpc.net/problem/1167

---

stonejjun님의 풀이(stonejjun.tistory.com/149)를 참고하여 해결하였습니다.

 

자세한 사항은 위 링크를 참고하시면 됩니다.

 

풀이를 요약하자면

 

1. 그래프(트리)를 만들면서 임의의 리프 노드 'A'를 하나 구합니다.

2. 'A'에서 DFS를 돌려서 'A'랑 가장 먼 거리의 노드인 'B'를 구합니다.

- 노드 'B'는 무조건 트리 지름의 한 점입니다.

3. 'B'에서 다시 DFS를 돌려서 'B'와 가장 먼 거리의 노드인 C'를 구합니다.

4. 'B'와 'C'의 거리가 트리의 지름이 됩니다.

---

코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ1167.cc