백준 1967 트리의 지름

www.acmicpc.net/problem/1967

1967번: 트리의 지름

무방향 그래프가 가중치를 포함하여 주어진 트리에서 트리의 지름을 구하는 문제이다.

지름은 가중치가 가장 긴 값이 지름이 된다.

문제는 이해가 되는데 트리의 지름에 대한 개념이 없어서 어떻게 풀어야 할지 감이 안 잡혀 다른 분들의 코드를 참고했다.

정해는 부모 노드에서 DFS를 돌려서 가장 큰 값이 나온 그 노드를 저장하고, 그 노드에서 다시 DFS를 돌려서 가장 큰 값이 나온다면 그 값이 지름이 된다.

문제 예시에서 보이듯 1에서 시작해서 DFS를 돌리면 9번 노드로 가게 될것이고, 9번 노드에서 DFS를 돌린다면 12번 노드로 갈 것이다.

 

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

bool vis[10001];
vector<pair<int, int>> ar[10001];
int ans, idx;

void dfs(int cur, int length) {
	if (vis[cur]) return;
	vis[cur] = true;
	if (ans < length) {
		ans = length; idx = cur;
	}
	for (auto i : ar[cur]) {
		dfs(i.first, i.second + length);
	}
}

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		int x, y, z; cin >> x >> y >> z;
		ar[x].push_back({ y,z });
		ar[y].push_back({ x,z });
	}
	dfs(1, 0);

	ans = 0;
	fill(vis, vis + 10001, false);

	dfs(idx, 0);
	cout << ans << endl;

	return 0;
}

 

어떻게 풀어야 할 지 알게 된 후 구현은 쉬웠던 것 같다.