(백준 1967번) 트리의 지름 증명

www.acmicpc.net/problem/1967

1967번: 트리의 지름

트리의 지름에 대한 조금 색다른 관점이 필요한 문제이다. 

 

 

  트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬수 없는 구조  이다. 

 

일단 왼쪽의 1~7 번의 동그란 점을 노드(Node)라고 하며 

                          주황색의 선들을 (Edge) 라고 한다. 

 

 

 

 트리는 다음과 같은 특징을 가진다.

 

1. 서로 다른 임의의 두 노드를 연결하는 경로는 유일하다. 

2. 트리에는 사이클이 존재하지 않는다. 

3. 트리에는 반드시 하나의 root 가 존재한다. 

 

본론으로 돌아가서 

백준 1967 번은 노드의 개수가 10000개임에 주목해야 한다. 

 

1번부터 N 번까지의 점까지 각점마다 dfs 로 탐색을 하며 

하나의 점마다 N 개의 점을 탐색하게 되면 N^2 의 시간이 걸리게 되어 

10000 x 10000 => 10억 번 연산을 하게 된다. 

 

즉 이문제에서는 새로운 방식으로 접근하는 시각이 필요한데 

여기에서 바로 트리의 지름을 간단하게 구하는 방법을 찾은뒤 그것을 증명할 예정이다. 

 

----------------------------------------------------------------------------------------

 

1. 임의의 하나의 점p를 잡고 해당점에서 가장 거리가 먼 점 t  를 잡는다. 

2. 정점 t 에서 가장 먼점 r 을 찾는다. 

3. t 와 r 사이의 거리는 트리의 지름이다 

----------------------------------------------------------------------------------------

dfs 두번으로 O(N^2) -> O(N) 만에 해결하는것은 좋은데 이것을 어떻게 증명하느냐는 것이다. 

 

아래 내용은 위 방법에 대한 증명 과정이다. 

 

귀류법으로 증명할 예정이다. 

 

점 p 에서 가장 먼점인 t 가 트리의 지름안에 존재할시 

t 에서 가장 거리가 먼점인 r 까지의 경로는 트리의 지름인 것은 자명하다. 

 

그렇다면 다음명제를 생각해보자 

 -> 점 p 에서 가장 거리가 먼점인 t 는 트리의 지름 안에 존재하지 않는다.

 

위 명제가 모순인 것을 증명할시  위에서 언급한 방법대로 구할시

트리의 지름을  O(N) 으로 구할수 있다는 것을 증명할수 있게 된다.

 

 

 ->"점 p 에서 가장 거리가 먼점인 t 는 트리의 지름 안에 존재하지 않는다." 

위 명제가 거짓임을 증명해보자 

 

(t,r) -> 실제 트리의 지름에 해당하는 양끝 경로

p -> 임의의 한점 

x -> p 에서 가장 거리가 먼점 

이때 x를 트리의 지름안에 존재하지 않는다고 가정해보자 -------①

 

 

#Case 1

p,x 사이의 경로가 실제트리의지름인 정점t,r 사이의 경로를 한점이상 공유하는경우 

임의의 두점 a,b 사이의 거리를 dist(a,b) 라 할시 

p에서 가장 먼점 x 라는 전제조건에 의해서 dist(p,m)+ dist(m,x) > dist(p,m)+dist(t,m)

이라는 것을 알수있으며 양변의 dist(p,m) 빼줄시  dist(m,x) > dist(t,m) --------②이라는 것을 알수있다.

②식의 양변에 dist(m,r) 을 더해줄시 

dist(m,r) + dist(m,x) > dist(t,m) + dist(m,r)  -----------③

이 되는데 이것은 ③ 의 우변이 트리의 지름, 즉 가장 긴변 이라는 가정에 어긋나기에 

 

X 가 트리의 지름안에 존재하지 않는다는 가정에 모순된다  

 

#Case 2

p,x 사이의 경로가 실제트리의지름인 정점t,r 사이의 경로와 독립될 경우

 

 

 

 

 

 

 

 

p,x,t, r 모두 독립될 경로를 가질시 

경로 px 위의 한점 a

경로 tr 위의 한점 b 

라고 가정하자 

 

 

 

p 에서 가장 먼 점 x 라는 전제 조건에 의해서 

dist(p,a) + dist(a,x) > dist(p,a) + dist(a,b) + dist(b,r) 이라는 것을 알수있는데 

양변에 dist(p,a) 삭제시 dist(a,x) > dist(a,b) + dist(b,r) 가 되고 

이는 dist(a,x) > dist(b,r)------④ 이라는 것을 증명한다. 

 

④식의 양변에 dist(t,b) 와 dist(a,b) 를 더할시 

 

 ⑤ - dist(t,b) + dist(a,b) + dist(a,x)  > dist(b,r) + dist(t,b) + dist(a,b) > dist(t,b) + dist(b,r) ==트리의 지름

이 되어 ⑤ 식의 좌변이 트리의 지름도 길게 되는 모순이 발생하기에 

 

X 가 트리의 지름안에 존재하지 않는다는 가정에 모순된다 

 

 

요약하자면 

시작점 P 에서 가장 먼점 t 는 트리의 지름안에 무조건 포함이 될수 밖에 없으며 

트리의 지름안에 포함되는 t 에서 가장 먼점 r 을 찾을시 dist(t,r) 은 트리의 지름에 해당할수밖에 없다는 내용이다. 

 

 

백준 1967번 코드는 밑에 추가하였다. 

#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>

using namespace std;

int N, Start, End, Distance, answer;

vector<pair<int, int> > vec[10004]; //vec[a]{b,c} a점에서 b점까지의 거리가 c이다.

									//중심축,현재탐색노드,현재까지구한 코스트

int find_longest(int point) {
	int ret = 0, maxi = 0;
	bool visit[10004];
	memset(visit, 0, sizeof(visit));

	queue<pair<int, int> > q; // (지금방문점,지금까지 얻은 거리)

	q.push({ point,0 }); visit[point] = true;

	//bfs 로 현재 점에서 주위 점들부터 q 에서 넣고 
	//방문했을시 건너뛰고 방문하지 않은 점일시 탐색해 가면서 
	//최장경로값은 maxi 에 저장하고 
	//maxi 저장할시 해당 방문점은 ret 에 저장한다. 
	while (!q.empty()) {
		int now = q.front().first;
		int nowdis = q.front().second;
		q.pop();

		if (maxi < nowdis) {
			ret = now;
			maxi = nowdis;
		}

		int vsize = vec[now].size();
		for (int i = 0; i < vsize; i++) {
			int next = vec[now][i].first;
			int nextdis = vec[now][i].second + nowdis;
			if (!visit[next]) {
				q.push({ next,nextdis });
				visit[next] = true;
			}
		}
	}
	answer = maxi;
	return ret;
}


int main() {
	cin >> N; N--;
	while (N--) {
		cin >> Start >> End >> Distance;
		vec[Start].push_back({ End, Distance });
		vec[End].push_back({ Start,Distance });
		//쌍방향 경로이기에 start 에서 end   사이의 거리는 Distance
		//                  end   에서 start 사이의 거리는 Distance
		//pair vector 배열에 삽입
	}

	int t = find_longest(1);
	int r = find_longest(t);

	cout << answer << "\n";
}