백준 1167 : 트리의 지름

오랜만에 알고리즘을 풀었다.

이 문제는 DFS를 이용해서 구한다.

처음에 모든 리프노드는 모두 루트노드가 될 수 있으니 리프노드를 전부 검색하는 방법으로 구현했지만 노드가 10만개라서 시간초과가 날 것이라 생각했다.

해결 방법으론 아무 리프노드나 골라 최대 경로를 구한 후 최대 경로의 끝 노드를 루트 노드로 다시 최대 경로를 구하면 된다. DFS 2번이면 해결 가능하지만 더 빠른 방법이 있을 것 같다.

 

#include<cstdio>	//
#include<vector>
using namespace std;

vector<pair<int, int>> tree[100001];
bool visits[100001];
int largest = 0;
int temp = 0;

bool isLeaf(int n){
	if(tree[n].size() == 1)
		return true;
	return false;
}

void dfs(int n, int length){
	if(length > largest) {
		largest = length;
		temp = n;
	}
	for(auto node : tree[n]){
		if(!visits[node.first]){
			visits[node.first] = true;
			dfs(node.first, length + node.second);
			visits[node.first] = false;
		} 
	}
}

int main(){
	int V;
	scanf("%d", &V);

	for(int i = 0; i<V; i++){
		int N, A, B; 
		scanf("%d", &N);
		
		while(1) {
			scanf("%d", &A);
			if (A<0) break;
			scanf("%d", &B);
			
			tree[N].push_back(make_pair(A,B));			
		}
	}

	for(int i=1; i<=V; i++){
		if(isLeaf(i)){
			visits[i] = true;
			dfs(i, 0);
			visits[i] = false;

			visits[temp] =true;
			dfs(temp, 0);
			visits[temp] = false;
			
			break;
		}
	}

	printf("%d", largest);
	return 0;
}