[백준/C++] 18126 너구리 구구

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

코드

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

typedef long long ll;

vector<vector<pair<int, ll>>> tree;
ll ans = 0;
vector<bool> visit(5001);

void dist(int start, ll len) {
	ans = max(ans, len);

	if (tree[start].empty()) return;
	else {
		for (int i = 0; i < tree[start].size(); i++) {
			int next = tree[start][i].first;
			int cost = tree[start][i].second;

			if (!visit[next]) {
				visit[next] = true;
				dist(next, len + cost);
			}
		}
	}
}

int main() {
	int n, target, now;
	cin >> n;

	tree.resize(n + 1);
	visit[1] = true;

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

		tree[a].push_back({ b, len });
		tree[b].push_back({ a, len });
	}

	dist(1,0);
	cout << ans;
	return 0;
}

 

설명

n을 입력받고 트리를 구성한다. 이후 dfs를 돌려서 계속 길이를 갱신해준다.

 

느낀 점

트리를 만들고 노드 간 거리가 가장 먼 노드를 찾아 거리를 출력하면 된다. 이전에 푼 문제보다 단순한 형태이기 때문에 빠르게 풀었다.