[Baekjoon,1967] 트리의 지름

트리의 지름을 찾기 위해서는 가장 멀리 떨어져 있는 두 노드를 찾아 두 노드의 거리를 구해야 한다. 이를 해결하는 방법은 먼저 루트에서 가장 멀리 떨어진 지점 $F$를 찾는다. 그 후 $F$를 루트로 두고 가장 멀리 떨어진 지점을 찾아 거리를 구하면 된다.
이에 대한 과정을 주어진 트리로 설명해보겠다.

//input
12
1 2 3
1 3 2
2 4 5
3 5 11
3 6 9
4 7 1
4 8 7
5 9 15
5 10 4
6 11 6
6 12 10
//output
//45

위와 같은 입력을 트리로 만들면 아래와 같다. 이때 루트는 1번 노드가 되며 루트와 가장 멀리 떨어진 노드는 거리가 28인 9번 노드이다.

그렇다면 9번 노드를 루트로 두고 노드의 위치만 바꿔 배치하면 아래와 같이 된다.

이때 9번 노드와 가장 멀리 떨어진 12번 노드와의 거리를 구하면 45가 나온다. 이것이 트리의 지름인 것이다.

---

구현

이에 대한 구현은 아래와 같다. 깊이 우선 탐색을 하며 가장 먼 지점까지의 값인 $longest$보다 더 먼 값이 나오면 $farthestNode$를 최신화 해주었다.
주의사항은 입력에 $n$이 1로 들어온 경우 트리의 지름이 0인것을 고려해야 하는 것이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX=10001;

int n;
vector<pair<int,int> > adj[MAX];
bool visited[MAX];
int farthestNode, longest;

void dfs(int here, int depth)
{
    if(visited[here])
        return;
    visited[here]=true;
    
    if(longest<depth)
    {
        longest=depth;
        farthestNode=here;
    }
    
    for(int i=0;i<adj[here].size();++i)
    {
        int there=adj[here][i].first;
        int nextDepth=depth+adj[here][i].second;
        dfs(there,nextDepth);
    }
}

int main()
{
    cin>>n;
    // 노드가 한 개인 경우 
    if(n==1)
    {
        cout<<0<<endl;
        return 0;
    }
    for(int i=0;i<n;++i)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        adj[a].push_back(make_pair(b,c));
        adj[b].push_back(make_pair(a,c));
    }
    memset(visited,false,sizeof(visited));
    dfs(1,0);
    
    memset(visited,false,sizeof(visited));
    dfs(farthestNode,0);
    cout<<longest<<endl;
    return 0;
}