트리. [1167]

[1. 문제 설명]

트리에서 임의의 두 점 사이의 거리 중 가장 긴 것의 길이를 출력한다.

(트리의 지름을 구한다.)

[2. 풀이 접근]

A. 잘못된 접근 방식 1

=> 모든 노드에서 DFS 를 수행한다.

=> 당연히 시간 초과 발생 (정점의 최대 개수는 200,000 개이므로, V^3 의 시간은 2초내에 풀 수 없다.)

B. 잘못된 접근 방식 2

=> 모든 edge 중 가중치가 가장 긴 것을 찾는다.

=> 이 edge 에 속한 노드 중 하나를 root 로 하여, bfs 수행

## 보통 트리의 지름은 leaf 에서 leaf 이므로, 가장 긴 edge 가 이 지름에 속할 것으로 생각함

## bfs 순회 중, root 에서 가장 먼 정점을 구할 수 있다.

## 방문 순서가 늦을 수록 root 에서 멀리 존재한다고 생각

=> root 에서 가장 먼 정점을 시작점으로 dfs 를 수행

이 풀이가 틀린 이유?

C. 올바른 접근 방식

[3. 코드]

[4. 기타 고찰]

입력으로 트리가 주어진다는 의미를 정확히 파악하지 못했다. (혹은 이 부분을 놓쳤다.)

cycle 이 있는 그래프 등을 생각하다 보니,

bfs 등으로 한차례 cycle 이 없는 그래프로 교체 후,

최장 경로를 판단하려고 했던 것이 하나의 큰 실수 였다.

트리의 정의를 명확히 아는 것 또한 중요함.

test_kernelv2