[백준] 1167 : 트리의 지름

url : https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

트리의 지름

leaf노드 ~ leaf노드까지의 거리 구하기

1. leaf 노드 구하기 (dfs)

2. leaf 노드에서 출발하여 dfs 최대 거리 구하기(leaf 노드 ~ leaf 노드)

 

코드

#include <bits/stdc++.h>
using namespace std;
int v, n, a, b, farthestNode, maxDistance;
vector<pair<int, int>> tree[100004];
int visited[100004];

void dfs(int node, int distance){
    if (distance > maxDistance){
        maxDistance = distance;
        farthestNode = node;
    }
    visited[node] = 1;
    for (auto &p : tree[node]){
        if (visited[p.first]) continue;
        dfs(p.first, distance + p.second);
    }
}


int main(){
    //1. 입력받기
    cin >> v;
    for(int i=0;i<v;i++){
        cin >> n;
        while(true){
            cin >> a;
            if (a==-1) break;
            cin >> b;
            tree[n].push_back({a, b});
        }
    }
    // 2. 가장 긴 노드 찾기
    dfs(1, 0);
    // 3. 가장 긴 노드로 최대 거리 = 트리의 지름 구하기
    maxDistance = 0;
    fill(visited, visited+100004, 0);
    dfs(farthestNode, 0);
    //4. 정답 출력하기
    cout << maxDistance;
}