[백준] 1967 : 트리의 지름

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

1967번: 트리의 지름

 

이 문제는 백준 1167 문제의 풀이와 거의 같다.

https://shout-to-my-mae.tistory.com/381

[백준] 1167 : 트리의 지름

 

다른 점은 리프 노드에서 리프 노드까지의 dfs를 수행하려면, 리프 노드1 -> 루트 노드 (위로 올라가기), 루트 노드 -> 리프 노드2(아래로 내려가기) 두 작업을 수행해야한다.

그렇기 때문에 자식 노드에서 부모 노드로 이어진 간선도 추가해야한다.

 

코드

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

void dfs(int node, int distance){
    visited[node]=1;
    if (distance > maxDistance){
        maxDistance = distance;
        farthestNode = node;
    }
    for (auto &p: tree[node]){
        if (visited[p.first]) continue;
        dfs(p.first, distance+p.second);
    }
}
int main(){
    //1. 입력받기
    cin >> n;
    for (int i=0;i<n-1;i++){
        cin >> a>> b>> c;
        tree[a].push_back({b, c}); // 부모 노드 -> 자식 노드
        tree[b].push_back({a, c}); // 자식 노드 -> 부모 노드
    }
    //2. 가장 끝 노드 구하기
    dfs(1, 0);
    //3. 초기화
    fill(visited, visited+10004, 0);
    maxDistance = 0;
    //4. leaf 노드에서 dfs 수행
    dfs(farthestNode, 0);
    //3. 정답 출력
    cout << maxDistance;
}