[Baekjoon] 트리의 지름

트리의 지름

📢 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 찾아라

---

📑 어떻게 해결할까?

DFS를 2번 해보자!!

1. 임의의 Node로부터 가장 먼 Node를 하나 찾고
2. 그 Node로부터 가장 먼 Node와의 거리를 찾자

Q. 아래 트리에서의 지름을 구해보아요.

문제에서는 Root가 주어져있지 않기 때문에 아무 Node나 Root로 잡아도 괜찮아요!

트리의 지름은 두 점 사이의 거리 중 가장 긴 것 즉, 각 Node 사이의 거리를 더해서 가장 긴 것을 찾아야 해요. 아래의 순서로 코드를 만들어서 문제를 해결하면 돼요.

1. 아무 Node를 Root로 잡아 DFS를 통해 Root로부터 가장 거리가 먼 노드를 찾아요.

2. 그 노드를 새로운 Root로 잡아서 DFS를 해요.

3. DFS를 통해 새로운 Root로부터 가장 큰 값을 가진 Depth를 구하면 됩니다.

---

📋 예제

백준 1167 - 트리의 지름

백준 1167 - 해답