1967 - 트리의 지름

풀이 : 가중치가 있는 트리의 지름을 구하는 것으로 처음에 접근을 잘못해서 애를 먹었지만 아이디어만 생각했으면 간단하게 dfs를 이용하여 풀 수 있는 문제 였다. 어렵게 생각하지말고 기초적인 것에서 약간 응용하는 방식으로 생각하는 것을 연습하기.

문제 코드

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

int n;
vector<pair<int, int>> tree[10001];
int ans;
int point;
int maxLen;
bool visited[10001];

void dfs(int node, int weight) {
	visited[node] = true;
	if (maxLen < weight) {
		maxLen = weight;
		point = node;
	}
	for (int i = 0; i < tree[node].size(); i++) {
		int x = tree[node][i].first;
		if (!visited[x]) {
			dfs(x, weight + tree[node][i].second);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		tree[a].push_back({b,w});
		tree[b].push_back({ a,w });
	}
	// 루트에서 가장 먼 노드(point) 찾기
	dfs(1,0);

	//init
	for (int i=0; i < 10001; i++) {
		visited[i] = false;
	}
	maxLen = 0;

	// point에서 가장 먼 노드가 지름이 된다.
	dfs(point,0);
	ans += maxLen;
	cout << ans;
	return 0;
}