취미로 코딩하기

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

이번에 볼 문제는 백준 1595번 문제인 북쪽나라의 도로이다.
문제는 아래 링크를 확인하자.

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

트리의 지름을 구하는 문제이다. 이 문제에서는 dp를 이용하여 트리의 지름을 구해보았다.

트리의 한 노드(1번)을 루트로 잡고, 다음과 같은 규칙을 생각하여 dp를 하자:

"현재 노드를 루트로 하는 서브트리에서, 이 루트를 지나는 최장경로의 길이는 가장 긴 두개의 자식방향의 경로 2개의 길이의 합과 같다"

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

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

vector<pair<int, ll>> G[10001];
bool visited[10001];

ll ans = 0;
ll dfs(int current, int parent) {
	ll ret1 = 0, ret2 = 0;
	for (auto np : G[current]) {
		int node = np.first; ll d = np.second;
		if (node == parent) continue;
		d += dfs(node, current);
		if (d > ret1) {
			ret2 = ret1; ret1 = d;
		}
		else if (d > ret2) ret2 = d;
	}
	ans = max(ans, ret1 + ret2);
	return ret1;
}

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

	int x, y; ll d;
	while (cin >> x >> y >> d) {
		G[x].push_back({ y,d });
		G[y].push_back({ x,d });
	}

	dfs(1, 0);

	cout << ans;
}