트리의 지름 구하기

트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다:

1. 트리에서 임의의 정점 $x$를 잡는다.

2. 정점 $x$에서 가장 먼 정점 $y$를 찾는다.

3. 정점 $y$에서 가장 먼 정점 $z$를 찾는다.

트리의 지름은 정점 $y$와 정점 $z$를 연결하는 경로다.

증명) 트리에서 정점 $u$와 정점 $v$를 연결하는 경로가 트리의 지름이라고 가정하자. 임의의 정점 $x$를 정하고, 정점 $x$에서 가장 먼 정점 $y$를 찾았을 때, 아래와 같이 경우를 나눌 수 있다.

i. $x$가 $u$ 혹은 $v$인 경우

ii. $y$가 $u$ 혹은 $v$인 경우

iii. $x$, $y$, $u$, $v$가 서로 다른 경우

자명하게 i., ii.에 대해서 위 알고리즘이 트리의 지름을 올바르게 구한다는 것을 알 수 있다. 이제 iii. 경우에 대해서 알고리즘이 트리의 지름을 올바르게 구한다는 것을 증명하면 된다. iii. 경우일 때 아래와 같이 두 가지 경우가 가능하다.

a. 정점 $x$와 정점 $y$를 연결하는 경로가 정점 $u$와 정점 $v$를 연결하는 경로와 한 점 이상 공유하는 경우

b. 정점 $x$와 정점 $y$를 연결하는 경로가 정점 $u$와 정점 $v$를 연결하는 경로와 완전히 독립인 경우

$d(s, t)$를 트리에서 정점 $s$와 정점 $t$의 거리라고 하자. a.의 경우 아래 그림에서 $d(t, y) = \max(d(t, u), d(t, v))$라는 것을 알 수 있다. 때문에 위 알고리즘은 트리의 지름을 올바르게 구한다.

b.의 경우 아래 그림과 같은 상황이 된다는 것인데 $u$에서 제일 먼 점이 $v$가 아니라 $y$가 되어 $u$와 $v$를 연결하는 경로가 트리의 지름이 된다는 가정에 모순된다. 때문에 b.의 경우는 불가능하다는 것을 알 수 있다.

때문에 소개한 알고리즘은 트리의 지름을 올바르게 구한다는 것을 증명했다.

#include <bits/stdc++.h> using namespace std; #define MAXN 300005 #define pb push_back #define sz(v) ((int)(v).size()) int N; int D[MAXN]; vector <int> con[MAXN], conv[MAXN]; int bfs(int s) { for (int i=1;i<=N;i++) D[i] = 2e9; queue <int> que; D[s] = 0; que.push(s); while (!que.empty()){ int q = que.front(); que.pop(); for (int i=sz(con[q]);i--;){ int t = con[q][i], v = conv[q][i]; if (D[t] < 2e9) continue; D[t] = D[q] + v; que.push(t); } } int ret = 1; for (int i=2;i<=N;i++) if (D[ret] < D[i]) ret = i; return ret; } int main() { scanf("%d", &N); for (int i=1;i<N;i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); con[a].pb(b); conv[a].pb(c); con[b].pb(a); conv[b].pb(c); } int y = bfs(1); int z = bfs(y); printf("%d <-> %d : %d\n", y, z, D[z]); }

저작자표시

'공부' 카테고리의 다른 글

Li Chao Tree (Dynamic Convex Hull Optimization)  (0)	2021.03.08
Stern-Brocot 트리  (0)	2019.05.21
트리의 지름 구하기  (4)	2016.10.11
Convex Hull Optimization  (4)	2016.08.23
가장 먼 두 점 구하기  (6)	2016.07.17
Building Heap in Linear Time  (2)	2016.07.01