TIL 23/02/17 트리의 지름 문제 (bfs)

[Aqusiz]

1967 트리의 지름(n=10,000)
1967 코드
1167 트리의 지름(n=100,000)
1167 코드

• 각 leaf node마다 dfs로 가장 먼 node 찾기 -> $O(N^2)$의 시간 복잡도를 가짐. c++로 해결할 수는 있으나 정해는 아니다

• 양방향 그래프로 만든 다음, bfs를 2번 사용 -> $O(N)$의 시간 복잡도

  1. root node(1번 node)로부터 가장 먼 leaf node를 탐색
  2. 해당 leaf node로부터 가장 먼 node 탐색