백준 1167 트리의 지름

문제링크

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

문제

풀이

처음에는 그냥 모든 단말노드에서 DFS를 돌려주어 트리의 지름을 찾으려 했다. 정점의 개수가 2<=V<=100000이니 당연히 시간 초과가 났다.
DP로 접근하려고도 생각해 보았는데 저 범위에서는 어차피 메모리 초과가 날것이므로 따로 시도는 안했다.
고민하던중 ..

임의의 한 점에서 가장 먼 거리에 있는 노드를 찾고 찾은 노드에서 가장 먼 거리에 있는 노드까지의 거리가 트리의 지름이 된다

는 힌트를 얻어 풀었다.
저 알고리즘만 알고 나면 나머지는 구현의 문제였다.

코드

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

vector<pair<int,int>> v[100001];

pair<int,int> solve(int now, int cost, int before) {

	bool is_leaf = true;
	pair<int, int> maxn = { 0,0 };
	for (int i = 0; i < v[now].size(); i++) {
		if (v[now][i].first != before) {
			is_leaf = false;
			pair<int,int> temp = solve(v[now][i].first, cost + v[now][i].second, now);
			if (temp.second > maxn.second) maxn = temp;
		}
	}

	if (!is_leaf) return maxn;
	else return { now,cost };
}

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

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;

		while (true) {
			int b, cost;
			cin >> b;
			if (b == -1) break;
			cin >> cost;
			v[a].push_back({ b,cost });
		}
	}

	pair<int, int> temp;
	temp = solve(1, 0, -1);
	temp = solve(temp.first, 0, -1);
	cout << temp.second;
}

후기

트리 지름 구하는 문제는 전에도 접한 적이 있는데 전에는 정점의 개수가 많지 않아 처음 시도했던 방법대로 모든 단말노드에서 DFS를 실행해 풀었었다.
이번 문제에서 트리의 지름을 구할 수 있는 간단한 방법을 알았으니 다음번에는 더 효율적으로 풀어보자.

+) 1967과 같은 문제이다.