백준 1967번 - 트리의 지름

트리의 지름

트리라는 자료구조는 사실 컴퓨터 공학을 전공했다거나, 알고리즘을 공부한다면 절대 안 배울 수 없는 자료구조이다.

정확히 트리가 무엇이냐, 정의가 분명 존재하겠지만
일단 사이클이 없는 그래프를 트리라고 생각하면 된다.
사이클이 없기 때문에, N개 노드에 대해 N-1개의 간선을 갖는다.

이러한 트리에 대해서 다양한 문제들이 존재하는데
대표적인게 이 트리의 지름에 관한 문제이다.
트리의 지름은 트리의 한 노드에서 가장 먼 다른 한 노드까지 가는 거리 를 말하는데

이를 구하는 방식은 대표적으로 두 가지가 있다.

1. 동적계획법을 이용한 방식
2. DFS를 이용한 방식

둘 다 O(n)의 시간복잡도를 가진다고 알려졌기에
둘 중 원하는 것을 쓰면 된다.

사실 저 둘 중 1의 방식은
일반화해서 모든 노드 x에서 가장 먼 거리에 있는 노드와 그 거리를 구하는데에도 쓰이지만,
이 문제에서는 루트 노드가 1이라고 정해져있기 때문에
dfs를 쓰는것이 가장 간단한 방법이다.

dfs로 트리의 지름을 구하는것은 다음과 같다.

1. 루트 노드에서 dfs를 통해 가장 멀리 있는 노드를 구한다
2. 1에서 구한 노드에서 가장 멀리있는 노드를 구한다
3. 이 때, 1에서 구한 노드와 2에서 구한 노드 사이 거리가 지름이다.

이것이 확 와닿지 않을 수 있지만, 트리를 쭉 펴서 직선으로 놓는다고 생각하면 꽤나 이해가 쉽게 된다.
이해가 안된다면 직선으로 트리를 한번 그려 보시기 바라며
코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<utility>
using namespace std;
vector<pair<int,int>> adj[10001];
int dist[10001]={0};
void dfs(int,int);
void initDist();
int main(){
	int n;cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b,c;
		cin>>a>>b>>c;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	dfs(1,0);
	int m = 0;
	int mValue=0;
	for(int i=1;i<=n;i++){
		if(mValue<dist[i]){
			m=i;
			mValue=dist[i];
		}
	}
	initDist();
	dfs(m,0);
	mValue = 0;
	for(int i=1;i<=n;i++){
		mValue=max(mValue,dist[i]);
	}
	cout<<mValue<<'\n';
    return 0;
}
void dfs(int start,int parent){
	if(adj[start].size()==0) return;
	
	for(auto s : adj[start]){
		int x = s.first;
		int y = s.second;
		if(parent==x) continue;
		dist[x]=dist[start]+y;
		dfs(x,start);	
	}
	return ;
}
void initDist(){
	for(int i=0;i<10001;i++){
		dist[i]=0;
	}
}