[백준 #1967 c++] 트리의 지름, 증명하기

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

이 문제는 웰노운에 속한다고 한다..

트리의 지름이란 문제에서 가중치의 합이 가장 큰 경로가 존재하며, 그 경로의 가중치를 말한다.

 

이번 리뷰는 문제풀이보다는 증명 위주이다.

 

자세한 증명 방법은 아래 블로그 주소를 참고바란다.

https://blog.myungwoo.kr/112

트리의 지름 구하기

 

위 포스팅에서 소개하는 증명 방법을 토대로 일부를 보완하여 설명해보자.

 

가정

가중치의 합이 가장 큰 경로의 시작점과 도착점을 각각 u, v 라고 한다.

임의의 정점 x에서 출발하여 가장 멀리 있는 정점 y를 택한다.

그리고 y에서 출발하여 가장 멀리있는 정점 z로 이동할 때 경로 y-z가 트리의 지름에 해당한다.

(x, y, z는 임의의 정점이며 u 또는 v가 될 수 있다.)

 

증명

1. 정점 x 또는 y가 정점 u 또는 v에 해당하는 경우 => 참

1) 정점 x가 u 또는 v인 경우
=> 도착점 역시 v 또는 u가 되므로 가정은 참이다.
2) 정점 y가 u 또는 v인 경우
=> y에서 출발하여 도착한 정점은 v 또는 u가 되므로 가정은 참이다.

 

 

2. 정점 x, y, u, v가 모두 다른 경우

 

2-1. 경로 x-y가 경로 u-v와 만나는 경우 => 모순 (존재하지 않음)

정점 x에서 출발하여 가장 멀리있는 정점 y에 도착하며
두 번째 출발지가 y가 되버린 이상 여기서 u에 도착하든 x에 도착하든 가장 긴 경로 u-v가 원의 지름이라는 말과 모순이 된다.
따라서 이 경우는 존재하지 않는다.

 

2-2. 경로 x-y가 경로 u-v와 만나지 않는 경우 => 모순 (존재하지 않음)

 

정점 x에서 출발하여 y에 도착하므로
경로 t-y는 경로 t-u와 경로 t-v보다 항상 더 길게 된다.

다시 정점 y에서 출발하면 x에 도착하므로
경로 t-x는 경로 t-u와 경로 t-v보다 항상 더 길게 된다.

즉 t-x와 t-y의 가중치 합은 항상 경로 t-u와 경로 t-v의 합보다 같거나 크다는 얘기가 되며
이는 마찬가지로 경로 u-v보다 경로 x-y가 더 길다는 말이 된다.

따라서 주어진 가정과 모순이 되며 이 경우는 존재하지 않는다.

 

정리

주어진 가정은 정점 x 또는 y가 정점 u 또는 v에 해당하는 경우만 존재하게 되고

이 가정은 참이다.

 

따라서

임의의 정점 x에서 출발하면 항상 원의 끝 점에 해당하는 u 또는 v에 도달한다.

 

---

다음은 코드이다.

// BOJ GOLD 4
// https://www.acmicpc.net/problem/1967

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> node[10001];
bool visited[10001];
int Max;
int End;

void dfs(int v, int sum) {
	if (visited[v]) return;
	visited[v] = true;
	
	if (Max < sum) {
		Max = sum;
		End = v;
	}
	
	for (int i = 0; i < node[v].size(); i++) {
		dfs(node[v][i].first, sum + node[v][i].second);
	}
}

int main(int argc, char** argv) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int n;
	cin >> n;
	while(--n) {
		int a, b, c;
		cin >> a >> b >> c;
		node[a].push_back(make_pair(b, c));
		node[b].push_back(make_pair(a, c));
	}
	
	dfs(1, 0);
	memset(visited, false, sizeof(visited));
	dfs(End, 0);
	
	cout << Max;
	
	return 0;
}

 

위의  가정을 토대로 dfs 탐색을 하면 된다.