P1167

[baekjoon-1167] 트리의 지름

풀이 과정

이 문제 풀다가 울 뻔 했다. 단순히 그래프 문제처럼 풀 것이 아니라, 트리의 성질을 이용해 시간복잡도를 생각해야 하는 문제이다.

1. 트리의 간선에는 방향이 없다.
2. 트리의 노드는 모두 연결되어 있다.

따라서 임의의 노드에서 가장 멀리 있는 노드를 찾고(루트 또는 리프 노드), 그 노드에서 가장 멀리 있는 노드를 다시 찾으면 임의의 두 점 사이의 가장 긴 거리를 구할 수 있다.

트리 문제를 더 많이 연습해보자.

2021.03.23

• 210323.java

다시 풀어도 또 루트를 먼저 찾는 풀이를 생각해내지 못하고 시간초과 이슈를 냈다. 더 연습하자.