[백준/C++] 1967. 트리의 지름

문제 

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

1967번: 트리의 지름

 

풀이 

처음에 문제를 봤을 때, 어떤 알고리즘을 이용해야 하는지 감이 오지 않았다. 그래서 검색을 좀 해보았는데, 공식처럼 트리의 지름을 구하는 알고리즘이 존재했고, 해당 알고리즘을 증명해놓은 글들도 많았다. 

https://blog.myungwoo.kr/112 (참고한 블로그)

 

[트리의 지름 알고리즘]

1. 임의의 정점 x를 잡는다. (보통 루트로 잡음)

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

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

4. 지름은 y-z 사이의 경로(거리)이다. 

 

그치만 내 머리로는 글로 된 증명을 이해할 수 없어서 직접 그림을 그려보았더니 이해가 되었다! 

 

아래 사진과 같은 트리가 있다고 하자! 그림에 표시한 y-z가 트리의 지름이다. 

루트를 x로 잡고 루트에서 가장 먼 정점 y를 찾고, y에서 가장 먼 정점 z를 찾으면 된다. 

그러면 이제, 같은 트리에서 진한 초록색 노드를 루트로 만들어보자 

그러면 아래 그림과 같은 모양이 된다. 이런 모양의 트리에서도 역시 루트를 x로 잡으면, 

x에서 가장 먼 z를 찾게되고, z에서 가장 먼 y를 구해서 z-y사이의 거리가 지름이 된다. 

증명이 좀 이상한거 같긴 하지만, 대강 그림을 그려보니 맞는 증명인거 같다! 라는게 결론이다..ㅎㅎ

 

그래서 이제 위의 알고리즘을 구현해야 하는데, DFS를 이용해서 구현할 수 있다. 

문제에 루트노드는 항상 1이라고 정해주었으니까 

1부터 DFS돌려서 가장 먼 노드를 찾고, 이렇게 찾은 가장 먼 노드로부터 다시 DFS를 돌리면, 둘 사이의 거리가 정답이다.

코드

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<pair<int,int>> graph[10001];
bool visited[10001] = { 0, };
int maxCost=0;
int node;

void DFS(int start, int cost) {
	visited[start] = 1;
	for (int i = 0;i < graph[start].size();i++) {
		if (!visited[graph[start][i].first]) {
			DFS(graph[start][i].first, cost+graph[start][i].second);
			if (cost+graph[start][i].second > maxCost) {
				maxCost = cost+graph[start][i].second;
				node = graph[start][i].first;
			}
		}
	}
}

int main() {
	cin >> N;
	for (int i = 0;i < N-1;i++) {
		int parent, child, cost;
		cin >> parent >> child >> cost;
		graph[parent].push_back(make_pair(child, cost));
		graph[child].push_back(make_pair(parent, cost));
	}

	DFS(1,0); //root에서 dfs

	//초기화 
	maxCost = 0;
	fill(&visited[0], &visited[10001],0);

	// root에서 가장 먼 node부터 다시 dfs
	DFS(node, 0);
	
	int result = maxCost;
	cout << result << endl;

	return 0;
}

결과