[BOJ] 1967번 트리의 지름 (C++)

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

1967번: 트리의 지름

 

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

int n;
vector<pair<int, int>> tree[10001];
bool visited[10001];

int max_len = 0;
int end_node = 0;

void dfs(int node, int len) {
	if (visited[node]) return;
	visited[node] = true;

	if (len > max_len) {
		max_len = len;
		end_node = node;
	}

	for (int i = 0; i < tree[node].size(); i++) {
		dfs(tree[node][i].first, len + tree[node][i].second);
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		tree[a].push_back({ b, c });
		tree[b].push_back({ a, c });
	}

	dfs(1, 0);  // 임의의 정점에서 가장 먼 정점 찾기
	max_len = 0;
	for (int i = 0; i < 10001; i++) visited[i] = false;
	dfs(end_node, 0);  // 위에서 찾은 정점에서 가장 먼 정점 찾기
	cout << max_len << '\n';
}

 

어떤 정점에서 출발해도 가장 멀리 있는 정점은 지름의 끝에 해당하는 두 정점 중 하나이다.

(참고: https://johoonday.tistory.com/224)

따라서 임의의 한 정점에서 dfs를 수행하여 가장 멀리 있는 정점을 찾은 후에

그 지점에서 dfs를 한 번 더 수행해 가장 먼 정점을 찾는다.