[백준] 1967-트리의 지름(C++)

문제링크:www.acmicpc.net/problem/1967

1967번: 트리의 지름

문제풀이를 위해선 

1.가장 깊은 노드 중 가중치가 가장 큰 노드를 찾는다.

2. 찾은 노드를 기준 정점으로 잡고, 다시 한번 가장 가중치가 큰 노드를 찾는다.

2가지를 수행하면 된다.

 

왜 이렇게 되는지에 대한 증명은 구사과님 글을 참고하자.

 

koosaga.com/14

트리의 지름 (Diameter of tree)

구현난이도는 쉽지만 아이디어 캐치가 어려운 문제였다.

이래서 개발자는 수학베이스가 있어야 하는것인가..

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int n = 0;
bool visited[10001] = { 0, };
vector <pair<int, int>> arr[10001];

int result = 0;
int destination = 0;

void dfs(int cur, int len) {

	if (result < len) {
		result = len;
		destination = cur;
	}

	for (int i = 0; i < arr[cur].size(); i++) {
		if (visited[arr[cur][i].first] == 0) {
			visited[arr[cur][i].first] = 1;
			dfs(arr[cur][i].first, len + arr[cur][i].second);
		}
	}


}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int s, e, v;
		cin >> s >> e >> v;
		arr[s].push_back(make_pair(e, v));
		arr[e].push_back(make_pair(s, v));
	}

	visited[1] = 1;
	dfs(1, 0); //목적지 구하고
	cout << result << endl;
	
	memset(visited, 0, sizeof(visited));
	result = 0;
	
	visited[destination] = 1;
	dfs(destination, 0);

	cout << result << endl;
	

}