[BOJ 18126 // C++] 너구리 구구

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 18126번 문제인 너구리 구구이다.
문제는 아래 링크를 확인하자.

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

18126번: 너구리 구구

주어진 N개의 방과 N-1개의 통로는 입구인 1번 노드를 루트로 갖는 트리와 같은 구조를 이루고 있음을 알 수 있다.

 

루트로부터 가장 멀리 떨어진 노드의 그 거리를 DFS등의 그래프 탐색으로 계산해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int N;
vector<pair<int,int>> G[5001];

ll dfs(int cur, int par) {
	ll ret = 0;
	for (auto& p : G[cur]) {
		if (p.first == par) continue;
		ret = max(ret, dfs(p.first, cur) + p.second);
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 1; i < N; i++) {
		int x, y, w; cin >> x >> y >> w;
		G[x].emplace_back(make_pair(y, w));
		G[y].emplace_back(make_pair(x, w));
	}

	cout << dfs(1, 0);
}