목록트리 (1)

hades

[Baekjoon] 1167번: 트리의 지름

🥅 문제https://www.acmicpc.net/problem/1167 🔍 설계가지가 1인 노드들에서 dfs를 이용하여 트리의 지름을 구하려고 했는데, 시간 초과가 발생하였다. 도저히 해결방법을 모르겠어서 레퍼런스 블로그를 참고하였다. 임의의 노드에서 가장 먼 노드를 구하고, 그 노드에서 가장 먼 노드를 구하면, 트리의 지름을 구할 수 있다고 한다.어떻게 이런 결과가 나오는지 공부해본다. 임의의 노드를 x라고 하고, x에서 가장 먼 노드를 y라고 하면, 3가지 경우가 있다.1) x가 트리의 지름의 양 끝 점 중 하나라면, x에서 가장 먼 노드인 y가 나머지 끝 점 중 하나가 되므로 y에서 가장 먼 노드(x)까지의 거리는 트리의 지름이 된다.2) y가 트리의 지름의 양 끝 점 중 하나라면, 당연하게 ..
👊 PS/Algorithm 2024. 8. 2. 21:48
이전 Prev 1 Next 다음