백준 1967번 - 트리의 지름

https://www.acmicpc.net/problem/1967

트리의 개념을 이해한 뒤에 DFS를 이용하여 문제를 해결하면 된다.

정답률이 40프로가 넘는데 몇시간을 고민해도 도저히 해결방법이 떠오르지 않아서 다른 사이트를 참고하다가

다른 분이 어떻게 문제를 해결했는지를 참고해서 문제를 풀었다.

아래에 나와있는 부분을 참고했는데 다른 분들이 해결한 방법도 거의 유사하다.

http://blog.sisobus.com/2013/10/backjoon-online-judge-no1967.html#.Wp58LiM68b1

먼저 가장 중요한 것은 트리가 방향성이 없고 모든 정점은 서로 연결되어 이어져 있다는 것이다.

문제를 해결할 때 특정 정점에서 한번 dfs를 돌아서 가장 멀리 있는 지점을 찾은 후에

그 지점에서 다시 dfs를 돌아서 가장 멀리 있는 지점과의 거리를 구하면 된다.

왜 dfs를 두번 돌아서 가야하는지  이해가 안되다가 다음과 같은 특징을 이해한 다음에 문제를 해결할 수 있었다.

하나의 정점에서 가장 멀리 있는 정점은 원의 지름 부분에 해당하는 정점이다.

그림에서 보듯이 원의 내부에서 가장 끝 점에 있는 두 지점이 지름에 해당한다.

그렇다면, 어떤 정점에서 출발을 해도 가장 멀리 있는 지점은 원의 지름에 해당하는 두 정점중에 하나일 것이다.

이해가 되지 않는다면 천천히 그림을 다시보며 과정을 떠올리면 이해할 수 있을 것이다.

다만, 어떤 정점에서 출발하냐에 따라서 가장 멀리있는 점은 달라질 수 있게 된다.

예를 들어 지름의 두 정점을 그림과 같이 평면 상에서 본다면

왼쪽 지점에서 출발한 정점과 가장 멀리 있는 지점은 오른쪽 부분에 있는 지름 길이의 정점이 될 것이고

오른쪽 지점에서 출발한 정점과 가장 멀리 있는 지점은 왼쪽 부분에 있는 지름 길이의 정점이 될 것이다.

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
 
int n;
int visited[10002]={0};
vector<pair<int,int>> node[10002];
 
int ans=0; //지름 길이
int end_point=0; //지름에 해당하는 끝점
void dfs(int point,int length){
    
    if(visited[point])
        return;
    
    visited[point]=1;
    if(ans<length){
        ans=length;
        end_point=point;
    }
    
    for(int i=0;i<node[point].size();i++){
        dfs(node[point][i].first,length+node[point][i].second);
    }
}
 
int main(){
    
    cin>>n;
    
    int parent,child,length;
    for(int i=0;i<n-1;i++){
        scanf("%d %d %d",&parent,&child,&length);
        node[parent].push_back(make_pair(child,length));
        node[child].push_back(make_pair(parent,length));
    }
    
    //가장 멀리 있는 정점(end_point) 구하기
    dfs(1,0);
 
    ans=0;
    memset(visited,0,sizeof(visited));
    
    //end_point와 가장 멀리 있는 정점과의 거리 구하기
    dfs(end_point,0);
    cout<<ans<<endl;
    
 
    return 0;
}