[Algorithm] 1967: TreeDiameter

📦1967: TreeDiameter

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-08 문제 확인하기

풀이

• DFS 를 2번 사용하는 방식이다.
• 구슬마다 서로 다른 길이의 실로 매달아놓고 한 구슬을 선택해 위로 들어올려 늘어뜨린다.
• 가장 거리가 먼 구슬을 선택해 다시 한 번 늘어뜨리면 트리의 지름이 나온다.

#include <iostream>
#include <vector>
#include <stack>
#define endl '\n';
using namespace std;
 
int V;
vector<pair<int, int>> vec[10001];
stack<pair<int, int>> st;
int vis[10002], res = 0;
 
void Initialize(){
    fill(vis, vis+10002, 0);
}
 
void Input(){
    cin >> V;
    for(int i = 1; i < V; i++){
        int start, end, dist;
        cin >> start >> end >> dist;
        vec[start].push_back({end, dist});
        vec[end].push_back({start, dist});
    }
}
 
int dfs(int start){
    st.push({start, 0});
    vis[start] = 1;
 
    int max_v = 0, max_dist = 0;
    
    while(!st.empty()){
        auto info = st.top(); st.pop();
        int prev_v = info.first;
        int prev_dist = info.second;
 
        if(max_dist < prev_dist){
            max_dist = prev_dist;
            max_v = prev_v;
        }
 
        for(auto nxt : vec[prev_v]){
            int cand_v = nxt.first;
            int cand_dist = nxt.second;
            if (vis[cand_v] == 1 || prev_v == cand_v) continue;
 
            st.push({cand_v, prev_dist + cand_dist});
            vis[cand_v] = 1;
        }
    }
    if(res < max_dist) res = max_dist;
    return max_v;
}
 
void Solution(){
    int max_v = dfs(1);
    Initialize();
    max_v = dfs(max_v);
    cout << res << endl;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Solution();
 
    return 0;
}