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

 

dfs 2번에 깔끔하게 풀리는 문제입니다. 풀이는 요기

#include <bits/stdc++.h>
using namespace std;


vector<pair<int, int>> graph[10000];	// idx, cost (root=0)
bool visited[10000];
int max_len;
int max_idx;

void dfs(int idx, int len) {
	if (max_len < len) {
		max_len = len;
		max_idx = idx;
	}

	for (auto& [next, nextDist] : graph[idx]) {
		if (!visited[next]) {
			visited[next] = true;
			dfs(next, len + nextDist);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		--a, --b;

		graph[a].emplace_back(b, c);
		graph[b].emplace_back(a, c);
	}

	dfs(0, 0);
	memset(visited, 0, sizeof(visited));
	dfs(max_idx, 0);
	cout << max_len << '\n';

	return 0;
}
반응형

'Online Judge > 백준' 카테고리의 다른 글

[백준][C++] 10707: 수도요금  (0) 2020.07.16
[백준][C++] 10173: 니모를 찾아서  (0) 2020.07.15
[백준][C++] 1520: 내리막 길  (0) 2020.07.14
[백준][C++] 19230: Datum  (0) 2020.07.14
[백준][C++] 19235: 모노미노도미노  (4) 2020.07.13