1967 트리의 지름

문제 설명

간선의 길이가 다른 트리가 있다고 가정할 때 두 리프노드를 선택해서 쭉 늘렸을 때 최대 길이를 구하는 문제

루트노드는 무조건 1이다

간선에 가중치가 다르기 때문에 1을 지나 가장 많은 노드를 통과한다고 해서 가장 긴 지름을 가진다고 할 수는 없다
(위의 그림과 같이 중간의 노드가 가장 위로 하여 지름을 만들 수 있음)

풀이

dfs를 이용하여 푸는 방식을 사용

한 노드에 도착했을 시

• 가장 긴 일직선 길이와 두번째로 긴 일직선 길이를 구한다
  (dfs방식으로 구해줌)

• 가장 긴 길이 + 두번째로 긴 길이
  = 해당 노드를 가장 위로 하는 최대 길이
  위의 값이 전역변수 MAX보다 크다면 갱신해줌

• 가장 긴 길이를 리턴하여 위의 노드에서 최대 길이를 사용할 때 사용한다

구현방법

pair을 사용한 vector을 이용하여 구현
벡터 배열 생성 후, 각 노드의 자식노드, 가중치를 pair로 묶어서 저장해둠

• 자식 노드의 개수가 0이라면 0을 리턴 (리프노드)

• first, second 변수를 0으로 초기화하고 자식 노드를 순환하면서 dfs(자식노드) + 가중치 의 값이

  • first보다 크다면 second를 first로 교체 & first 값을 위의 값으로 교체
  • second보다 크다면 second 값을 위의 값으로 교체

• first + second 가 MAX 보다 크다면 MAX 값 갱신

코드

#include <stdio.h>
#include <vector>

using namespace std;
vector<pair<int,int> > v[10001];
int MAX =0;
int dfs(int x){
	if(v[x].size()==0){ // 리프노드 
		return 0;
	}
	int first =0;
	int second =0;
	for(int i=0;i<v[x].size();i++){
		int sum = v[x][i].second + dfs(v[x][i].first);
		if(sum>first){
			second = first;
			first = sum;
		}else if(sum>second){
			second = sum;
		}
	}
	if(first + second > MAX){
		MAX = first + second;
	}
	return first;
}
int main(){
	int num;
	int t1,t2,t3;
	scanf("%d",&num);
	for(int i=0;i<num-1;i++){
		scanf("%d %d %d",&t1,&t2,&t3);
		v[t1].push_back(make_pair(t2,t3));
	}
	
	dfs(1);
	printf("%d",MAX);
}