백준 1967(트리의 지름)

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

1967번: 트리의 지름

 

트리의 지름

 

트리에서 가장 먼 거리의 두 지점을 이은 거리가 그 트리의 지름이다. 

 

https://blog.myungwoo.kr/112

트리의 지름 구하기

이 블로그의 수학적 증명을 참조하였다

 

트리의 지름 구하는 법은 엄청 단순하다 

아무 지점이나 잡고, 그 지점에서 가장 먼 지점을 구하고, 그 지점에서 가장 먼 곳까지의 거리가 트리의 지름이다. 

 

그렇다면 문제는 어떻게 풀까. 

 

트리 문제라고 트리 구조체를 통해서 풀까 생각을 해봤는데 의미가 없다 이 문제의 요구사항에는 자식/부모의 구별의 필요가 없기 때문이다. 따라서 수직적 구조가 아닌 단순하게 인접 리스트로 트리를 구현할 수 있었다. 

 

그 뒤에 dfs로 푼다. dfs로 접근한 이유는 거리계산이 간편하고, 완전탐색이 필요했기 때문이다. dfs는 모든 지점을 탐색해준다. 

 

먼저 깊이가 깊은 곳까지 들어간뒤에 가장 깊은 곳부터 다시 거꾸로 나오는 방식이다. 

 

그래서 함수를 돌리다가 전에 구했던 거리보다 더 멀다면 그 거리를 수정해주고, 1(root)에서 가장 먼 지점 x를 찾기 위해서 x도 최신화 해주었다. 

 

결국에는 ans 에 최대거리, x에 root에서 최대거리때의 지점이 저장된다.

 

x에서의 최대거리가 트리의 지름이 된다. 

 

#include<iostream>
#include<vector>
#include<utility>
using namespace std;
#define MAX 10001

int N, a, b, c, x, ans;
vector<pair<int, int> > node[MAX];

void dfs(int w, int cur, int prev = -1) {
	if (ans < w) {
		ans = w; 
		x = cur;
	}
	for (int i = 0; i < node[cur].size(); i++) {
		int next = node[cur][i].first;
		int d = node[cur][i].second;
		if (next == prev) continue;
		dfs(w + d, next, cur);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i < N; i++) {
		cin >> a >> b >> c;
		node[a].push_back(make_pair(b, c));
		node[b].push_back(make_pair(a, c));
	}
	dfs(0, 1); 
	ans = 0;
	dfs(0, x);
	cout << ans;
}