백준 1967. 트리의 지름

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

모든 리프 노드들에 대하여 깊이 우선 탐색으로 다른 노드들까지의 거리를 구하면 된다. 

구한 거리중 가장 큰 값이 답이다.

 

 

 

---

풀고난후 다른 분들의 코드를 살펴봤는데 트리의 지름을 구하는 방법이 있었다.

 

1) 임의의 노드 a에서 가장 먼 노드b를 찾는다. 

위 그림에서 임의의 노드를 5로 정하면 가장 먼 노드는 거리 11+9+10=30인 노드 12이다. 

 

2) 찾은 노드 b에서 가장 먼 노드 c를 찾는다.

b노드는 12이고 이 노드에서 가장 먼 노드는 거리 10+9+11+15=45인 9이다.

 

3) b-c가 트리의 지름이다.

 

 

이 방법으로 구하면 두번의 dfs로 답을 구할수 있을 것이다.