(알고리즘) 트리의 지름 구하기 및 증명!!!!
트리에서 정점 두개를 잡고 거리를 구한다.
그런데 이렇게 되면 O(n^2)이된다.
하지만 dfs 2번 돌려서 O(n)에 해결할 수 있다.
1. 아무 정점(루트)를 잡고 , 이 점에서 가장 거리가 먼 점 t를 잡는다.
2. t에서 가장 거리가 먼 점 u를 찾는다.
3. t~u가 트리의 지름. 끝
(증명): https://www.quora.com/How-does-following-algorithm-for-finding-longest-path-in-tree-work
따라서 이러한 점 C는 존재하지 않는다.
문제: https://www.acmicpc.net/problem/1167
그런데 이렇게 되면 O(n^2)이된다.
하지만 dfs 2번 돌려서 O(n)에 해결할 수 있다.
1. 아무 정점(루트)를 잡고 , 이 점에서 가장 거리가 먼 점 t를 잡는다.
2. t에서 가장 거리가 먼 점 u를 찾는다.
3. t~u가 트리의 지름. 끝
(증명): https://www.quora.com/How-does-following-algorithm-for-finding-longest-path-in-tree-work
따라서 이러한 점 C는 존재하지 않는다.
문제: https://www.acmicpc.net/problem/1167
댓글
댓글 쓰기