(C++) 백준 1967 트리의 지름

문제 및 풀이

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

• 임의의 노드에서 가장 먼 노드 x를 찾는다
• x에서 가장 먼 노드 y까지의 길이가 트리의 지름이다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;




int main() {
    int n; cin>>n;

    vector<pair<int, int>> tree[n+2];
    vector<bool> isVisited(n+2, false);

    int a,b,c;
    for(int i=1; i<n; i++){
        cin>>a>>b>>c;
        tree[a].emplace_back(b,c);
        tree[b].emplace_back(a,c);
    }
 
    queue<pair<int, int>> q;
    q.push({1,0});
    isVisited[1]=true;

    int MAX_node=0;
    int MAX_cost=0;

    while(!q.empty()){
        int node = q.front().first;
        int cost = q.front().second;
        q.pop();

        for(int i=0; i<(int) tree[node].size(); i++){
            int next = tree[node][i].first;
            int next_cost = cost + tree[node][i].second;

            if(isVisited[next]) continue;
            isVisited[next] = true;

            if(next_cost>MAX_cost){
                MAX_cost = next_cost;
                MAX_node = next;
            }
            q.push({next, next_cost});
        }
    }


    for(int i=1; i<n+2; i++) isVisited[i]=false;
    q.push({MAX_node, 0});
    isVisited[MAX_node] = true;
    MAX_cost=0;

    while(!q.empty()){
        int node = q.front().first;
        int cost = q.front().second;
        q.pop();

        for(int i=0; i<(int) tree[node].size(); i++){
            int next = tree[node][i].first;
            int next_cost = cost + tree[node][i].second;

            if(isVisited[next]) continue;
            isVisited[next] = true;

            if(next_cost>MAX_cost){
                MAX_cost = next_cost;
                MAX_node = next;
            }
            q.push({next, next_cost});
        }
    }


    int ans =MAX_cost;
    cout<<ans;

}