백준 1967 C++ 준코

#include <iostream>
#include <vector>

using namespace std;

int n ;

vector<pair<int,int>>graph[10001];
int visited[10001];

int m =0 ;
int endpoint=0;
void dfs(int start, int len){

    visited[start] = 1 ;

    if(m < len){
        m = len;
        endpoint = start;
    }

    for(int i =0 ; i < graph[start].size();i++){
        int next = graph[start][i].first;
        if(visited[next]==0){
            dfs(next,len+graph[start][i].second);
        }
    }
}


int main(){
    cin >> n;

    for(int i = 0 ; i < n-1;i++){
        int a,b,c;
        cin >> a>> b>> c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});

    }

    dfs(1,0);
    m=0;
    memset(visited,0,sizeof visited);
    dfs(endpoint,0);
    cout << m;



}

트리의 지름을 구하는 문제

- 1번째 노드에서 제일 먼곳으로 간 후에 그곳에서 또 제일 먼곳을 검사하면 트리의 지름이 된다. 즉 dfs를 두번 돌리면 된다

1. dfs 돌리면 가중치의 합들 중 가장 큰값을 계속 m에 저장을 해 준다.

2. 끝까지 돌리면 dfs 루트 중에 가장 큰 거리값이 남는다.

3. 가장 큰 거리값을 가진 endpoint를 시작으로 dfs를 다시 돌려준다 . 이때 시작 가중치는 0 으로 한다.

4. 다시 dfs를 돌려서 endpoint에서부터 가장 큰 거리 가중치값을 가진 값이 바로 정답이 된다.

(1번노드에서 -> 가장 먼곳으로 , 가장 먼끝점에서 다시 가장 먼 끝점으로 갔기 때문에)