BOJ 1167 - 트리의 지름

12 Mar 2017 on Algorithm

출처 BOJ

트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다)

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4과는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

예제

범위체크

최대거리( $10^{4}$ ) x 모든 노드 개수( $10^{5}$ ) $= 10^{9} \le INT$

풀이

루트에서 각 노드로 가는 거리 구하기
가장 긴 거리의 노드에서 다른 모든 노드로 거리 구하기
→ 최대 값이 지름
코드
code

#include<cstdio>
#include<vector>
#include<queue>
#include<iostream>
#define BOUND 100001

using namespace std;

vector<pair<int,int> > G[BOUND];
int V;
int MAX = 0;
int Idx = 0;
queue<pair<int,int> > Q;
int check[BOUND];

void bfs(){
	while(!Q.empty()){
		int node = Q.front().first;
		int val = Q.front().second;
		Q.pop();
		for(auto it=G[node].begin(); it!=G[node].end(); ++it){
			int next = (*it).first;
			if(check[next] == 0){
				check[next] = 1;
				int sum = (*it).second + val;
				Q.push(make_pair(next,sum));
				if(MAX < sum){
					MAX = sum;
					Idx = next;
				}
			}
		}
	}
}

int main(){
	scanf("%d",&V);
	for(int i=0; i<V; i++){
		int root, node, weight;
		scanf("%d",&root);
		while(1){
			scanf("%d",&node);
			if(node == -1)
				break;
			scanf("%d",&weight);
			G[root-1].push_back(make_pair(node-1,weight));
		}
	}

	for(int i=0; i<2; i++){
		fill_n(check,V,0);
		MAX = 0;
		Q.push(make_pair(Idx,MAX));
		check[Idx] = 1;
		bfs();
	}

	printf("%d\n",MAX);
}

복잡도

$O(2(V+E)) = O(V+E)$
bfs를 2번 도는 코드이고 linked list로 구성된 그래프기 때문에