[자료구조] 트리의 지름

reference : 최동완 교수님 강의

트리의 지름

자료구조 트리에 대해서는 알고 있었다.
그런데 오늘 트리에도 "지름"이라는 것이 존재한다는 것을 처음 알게 됐다

트리는 그래프 중에서 사이클이 없는 것을 말한다.
트리의 지름은 트리의 노드 중, 가장 먼 노드 끼리의 거리를 말한다.

아래와 같이 사이클이 없는 그래프에서, 트리의 지름의 개념을 이용해 서로의 길이가 최장거리인 노드 두 개를 찾을 수 있다.

그림에서, 6번 노드와 10번 노드의 거리가 4+3+2+3+5 = 16으로 가장 길다.
루트 노드가 무엇인지 모르는 상황에서도, 이 그래프의 최장거리는 구할 수 있다.
다음과 같은 로직으로 위 그래프 노드 사이의 최장거리를 구할 수 있다.

1. 임의의 노드(A)에서 DFS 혹은 BFS를 수행하여, 그 노드에서 가장 먼 노드(B)를 탐색한다.
2. 검색 결과인 노드 B에서 다시 DFS 혹은 BFS를 수행하여 노드 B에서 가장 먼 노드 C를 탐색한다.
3. 노드 B와 C가 지름을 이루게 된다.

C++ 코드

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

pair<int, int> bfs(vector<pair<int, int>>* graph, bool *visit, int start){
    // 노드 번호, 거리
    queue<pair<int, int>> q;
    // start번 에서 시작
    q.push(pair<int, int>(start, 0));
    visit[start] = true;
    // start번에서 가장 먼 노드 번호, 거리
    pair<int, int> far;
    far.first = 0;
    far.second = 0;
    
    while(!q.empty()){
        int num = q.front().first;
        int dist = q.front().second;
        q.pop();
        
        for(int i=0; i<graph[num].size(); i++){
            int now = graph[num][i].first;
            if(!visit[now]){
                q.push(pair<int, int>(now, dist + graph[num][i].second));
                visit[now] = true;
                if(dist + graph[num][i].second > far.second){
                    far.first = now;
                    far.second = dist + graph[num][i].second;
                }
            }
            
        }
    }

    return far;
}

void diameter(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 이웃 노드 번호, 거리
    vector<pair<int, int>> graph[20001];
    // bfs 방문 여부
    bool visit[20001];
    for(int i=0; i<20001; i++){
        visit[i] = false;
    }
    
    int n;
    cin>>n;
    
    // graph 세팅
    for(int i=0; i<n-1; i++){
        int u, v, d;
        cin>>u>>v>>d;
        graph[u].push_back(pair<int, int>(v, d));
        graph[v].push_back(pair<int, int>(u, d));
    }
    
    // 임의의 노드 1번에서 가장 먼 노드 탐색
    pair<int, int> one = bfs(graph, visit, 1);
    
    // 그 노드에서 한번 더 bfs 탐색
    for(int i=0; i<20001; i++)
    {
        visit[i] = false;
    }
    
    pair<int, int> two = bfs(graph, visit, one.first);
    
    // 그래프의 지름을 출력
    cout<<two.second<<'\n';
}



int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    // 테스트 케이스
    int T;
    cin>>T;
    
    while(T > 0){
        diameter();
        T--;
    }
    
}