1967_트리의 지름

▶ 골드4 (트리)

풀이

노드들의 가중치 합 중 최댓 값을 구하는 문제인데, 중요한 것은 꼭 루트 노드를 포함해야할 필요가 없다.

그래서 모든 노드를 기준으로 dfs를 진행해서 가중치 최댓값을 구하면 된다.

 

코드

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#define MAX 10001
using namespace std;

int n;
vector <pair<int, int>> graph[MAX];
bool visited[MAX];
int ans;

void dfs(int i, int value) {
	visited[i] = true;

	if (value > ans) {
		ans = value;
	}

	for (int j = 0; j < graph[i].size(); j++) {
		int u = graph[i][j].first;
		int v = graph[i][j].second;

		if (!visited[u]) {
			dfs(u, value + v);
		}
	}
	
}

int main() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({ b, c });
		graph[b].push_back({ a, c });
	}

	for (int i = 1; i <= n; i++) {
		dfs(i, 0);
		memset(visited, false, sizeof(visited));
	}
	cout << ans << endl;
}