BOJ 1167 트리의 지름

사용한 알고리즘

분할정복, DFS

알고리즘 설명

트리의 관계를 이용하여 그래프를 구성한다.
트리의 지름은 각 노드에서 각 두 자식에서 얻어지는 가장 긴 길이를 더한 합이다.
각 노드에서 부모로 가는 경로는 부모에서 자식을 보는 경우와 겹치기 때문에 보지 않아도 된다.
부모에게 자신의 자식중 가장 긴 길이를 알려주기 위해서 자식중 가장 긴 길이를 부모에게 알려준다.
위와 같은 형태로 문제를 부모와 자식으로 분할하고 문제를 정복해간다.

풀이

// baekjoon 1167 yechan
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
const int MAX_V=100001;
typedef pair<int, int> P;

int V, ans;
vector<P> adj[MAX_V];
bool visited[MAX_V];

int dfs(int here) {
	visited[here]=true;
// maxVtx는 자식 중 가장 긴 길이
// secVtx는 자식 중 두번째로 긴 길이
	int maxVtx=0, secVtx=0;
	int ret=0;
	for (int i=0; i<adj[here].size(); i++) {
		if (visited[adj[here][i].first]) continue;
		ret=dfs(adj[here][i].first) + adj[here][i].second;
		if (ret > maxVtx) {
			secVtx = maxVtx;
			maxVtx = ret;
		} else if (ret > secVtx){
			secVtx = ret;
		}
	}
// 두 자식의 합이 현재 노드에서 얻어질 수 있는 최대 길이 지름
	ans = max(ans, maxVtx+secVtx);
// 자식중 가장 긴 길이를 반환
	return maxVtx;
}

int main() {
	scanf("%d", &V);
// 그래프 구성
	for (int i=0; i<V;i++) {
		int node, v, w;
		scanf("%d", &node);
		while (1) {
			scanf("%d", &v);
			if (v == -1) break;
			else {
				scanf("%d", &w);
				adj[node].push_back(P(v,w));
			}
		}
	}
// 루트(1)로 부터 가장 긴 길이를 찾아옴
	dfs(1);
	printf("%d\n", ans);
	return 0;
}