시간 제한: 2초, 백준 1167번

트리의 지름 : 트리를 구성하는 노드 중 두 노드 사이의 거리가 가장 긴 것을 말한다.

Q1) 왜 이 문제에서는 BFS를 사용했을까?

✅ 1. DFS보다 BFS를 사용할 때의 이점

DFS도 트리 탐색이 가능하지만, 이 문제에서는 BFS가 더 유리한 이유가 몇 가지 있습니다:

1. 스택 오버플로우 방지:

   트리 노드 수는 최대 100,000개입니다.

   DFS는 재귀 호출을 이용하므로 깊이가 깊어질 경우 스택 오버플로우가 발생할 수 있습니다.

   반면 BFS는 큐를 이용한 반복문 기반이므로 이런 위험이 없습니다.

2. BFS는 최단거리 탐색에 직관적:

   BFS는 너비 우선 탐색이라 출발 노드로부터의 거리 계산이 간단합니다.

   BFS로 탐색하면서 거리 배열을 채우면, 한 번의 탐색으로 모든 노드까지의 거리 계산이 끝납니다.

3. 구현이 간결하고 효율적:

   DFS도 가능하지만, BFS가 재귀 없이 반복문으로 구성되기 때문에 메모리와 시간 모두에서 안정적입니다.

Q2) 왜 BFS를 두 번 수행할까?

✅ 2. BFS를 두 번 수행하는 이유

트리의 지름을 구하는 대표적인 방법은 BFS 두 번입니다. 이유는 다음과 같습니다:

✔️ 첫 번째 BFS

• 트리의 임의의 노드(예: 1번 노드)에서 시작하여 모든 노드까지의 거리를 구합니다.
• 이때 가장 멀리 있는 노드 A를 찾습니다.
  • 이 노드는 트리의 한 쪽 끝점일 가능성이 높습니다.

✔️ 두 번째 BFS

• 첫 번째 BFS에서 찾은 노드 A를 시작점으로 다시 BFS를 수행합니다.
• 이번에는 노드 A로부터 가장 멀리 있는 노드 B까지의 거리를 구합니다.
  • 이 거리(A ↔ B)가 바로 트리의 지름입니다.