할머니의 콤퓨타 도전기

트리의 지름 증명 본문

Algorithm/Algorithm 정리

트리의 지름 증명

ji.o.n.e 2021. 1. 17. 16:54

트리의 지름

  • 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것

트리의 지름 구하는 방법

  1. 임의의 점(A)에서 가장 먼 지점 B를 찾음
  2. B에서 가장 먼 지점(C)를 찾음
  3. B~C의 거리가 트리의 지름

증명 (귀류법)

출처: https://blog.naver.com/adamdoha/222121145206

관련 문제

 

1167번: 트리의 지름

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지

www.acmicpc.net

 

저작자표시

'Algorithm > Algorithm 정리' 카테고리의 다른 글

Knapsack 알고리즘  (0) 2021.01.30
다익스트라(Dijkstra) 알고리즘  (0) 2021.01.26
분할 정복 (Divide & Conquer)  (0) 2021.01.15
백트래킹 (Backtracking)  (0) 2021.01.11
그리디 (Greedy) 알고리즘  (0) 2021.01.08
'Algorithm/Algorithm 정리' Related Articles more
Comments