사용자 도구

사이트 도구


ps:트리

트리

순회

트리의 지름

  • 정의는 '트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이'
  • 구하는 방법은 그래프 탐색을 이용하는 방법과, tree dp를 이용하는 방법이 있다. 그래프 탐색을 이용하는 방법이 더 심플하게 구현 가능.
  • 그래프 탐색을 이용하는 방법은
    • 1) 임의의 노드 v0를 잡는다.
    • 2) v0에서 가장 먼 노드 v1을 찾는다.
    • 3) v1에서 가장 먼 노드 v2을 찾는다.
    • 4) v1에서 v2까지의 길이가 트리의 지름.
    • 이 알고리즘의 타당성 증명은 간단하다. 여기 참고
  • Tree DP를 이용하는 방법은
    • dp[v]를 v의 자손인 리프 노드들중, 가장 먼 노드까지의 거리라고 정의하면, dp[v] = max(dp[child] + dist[v][child])로 계산 가능
    • 또한 dp2[v]를 v의 자손인 리프 노드들중, 두번째로 먼 노드까지의 거리라고 정의하면, 이것도 같이 구할 수 있다.
    • 트리의 지름은 max(dp[v] +dp2[v])이 된다.
  • 트리의 지름에 해당하는 모든 경로는 트리의 중앙지점(centroid)를 지난다. 이것 역시 증명은 어렵지 않다.

예제 문제

토론

댓글을 입력하세요:
I H V H D
 
ps/트리.txt · 마지막으로 수정됨: 2021/01/16 16:56 저자 teferi