트리의 지름1 [백준] 1967. 트리의 지름 (C++) Key양의 가중치가 있는 트리가 주어졌을 때 두 노드 사이의 경로 중 가장 긴 경로 구하기노드 개수는 최대 1만개루트 노드는 항상 1번 Idea트리의 지름을 구하는 방법은 다음과 같다.루트 노드에서 가장 먼 노드 A를 찾는다.노드 A에서 가장 먼 노드 B를 찾는다.A와 B 사이의 경로가 트리의 지름이 된다. 이 문제는 DFS를 두번 활용하면 된다. 우선 두 노드 중 첫번째 노드를 구해보자. 편의상 두 노드를 A, B라고 하겠다. A노드는 루트노드에서 가장 먼 노드를 찾으면 된다. 처음에 왜 루트 노드에서 가장 먼 노드가 A가 되는건지 이해를 못했는데, 간선의 가중치가 양의 정수라서 그렇다. 때문에 거치는 간선 개수가 많아질 수록 경로 길이도 길어진다. 따라서 말단 노드 중 하나가 A 노드일 확률이 높고,.. 2024. 7. 14. 이전 1 다음