[백준,c++] 1967번 - 트리의 지름

문제

1967번: 트리의 지름

 

코드

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

int max_len = 0;
int max_node;
bool visited[10001];
int ans;
vector<pair<int,int>>graph[10002];

void dfs(int node, int len){
    visited[node] = 1;
    
    if(max_len<len){
        max_len = len;
        max_node = node;
    }
    
    for(auto next: graph[node]){
        if(!visited[next.first]){
            visited[next.first] = 1;
            dfs(next.first, next.second+len);
            visited[next.first] = 0;
        }
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; 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);
    max_len = 0;
    memset(visited,0,sizeof(visited));
    dfs(max_node, 0);
    ans += max_len;
    
    cout<<ans;
}

 

풀이

 

풀이 아이디어는 루트 노드에서 길이가 가장 긴 노드를 찾은 뒤, 그 노드로부터 가장 긴 노드로 가는 길이를 기억하는 것입니다.

위 사진에서는 1번 노드에서 시작하여 9번노드를 찾은뒤, 9번노드부터 12번 노드까지 이어지는 간선을 전부 더하는 것입니다.

1. 먼저 루트노드는 항상 1번임을 문제에서 명시되어 있습니다. 
2. 루트 노드를 기점으로 최대 간선 길이를 갱신해가며 리프 노드를 찾습니다.
3. 그 리프노드로부터 가장 긴 간선을 가진 리프 노드가 나올 때까지 간선의 길이를 더합니다.