[백준 1167] 트리의 지름 C++

1167번: 트리의 지름

트리, DFS

약 7개월 전에 자료구조 수업에서 트리를 공부하고 풀어보려고 시도했었지만 실패했었던 문제

알고리즘 수업에서 트리의 지름을 구하는 '머리끄댕이' 알고리즘을 배우고 이 문제가 생각나서 적용해서 풀어보았더니 바로 풀림!

---

1. 문제 해결 아이디어

트리의 지름을 구하기 위한 ㅈㅎㄱ 교수님의 '머리끄댕이' 알고리즘을 알아보자

 

 

이러한 트리가 존재하고 지름을 구하기 위해 쭉 늘려보았다

 

 

여기서 X는 트리에 있는 임의의 정점이다.

X를 잡고 쭉 늘어뜨리면 가장 밑에 있는 정점이 있기 마련이다.

 

가장 밑에 있는 정점을 U라고 하자

 

만약 정점간의 거리가 주어져 있다면 U는 X로 부터의 거리의 총합이 가장 긴 정점이 될 것이고, (DFS사용)

정점간의 거리가 주어지지 않았다면 BFS를 통해 구할 수도 있고, X로부터 가장 멀리 떨어진 정점이 될것이다.

 

여기서 U를 잡고 다시 트리를 늘어뜨려보자 (두 번째 DFS)

 

가장 밑에 있는 정점을 V라고 하자.

 

위와 같은 방식으로 V에서 가장 거리가 먼 정점을 구할 수 있을 것이다. 

 

이때 U와 V가 지름을 이루는 두 정점이 됨이 자명하고,

두 번째 DFS(정점의 거리가 주어져 있을 때)를 통한 최대 거리가 트리의 지름이 된다.

---

2. 코드

 

#include <bits/stdc++.h>
 
#define pii pair<int, int>
 
using namespace std;
 
vector< pii > tree[100001];
int visited[100001];
int max_dist = 0;
int farthest_leaf;
 
 
void dfs(int now, int dist){
    if(dist > max_dist){
        max_dist = dist;
        farthest_leaf = now;
    }
    
    visited[now] = true;
    
    for(int i = 0; i < tree[now].size(); i++){
        int next = tree[now][i].first;
        int nwei = tree[now][i].second;
        
        if(visited[next]) continue;
        dfs(next, dist + nwei);
    }
    
}
 
void input(){
    int N, apex, to, wei;
    cin >> N;
    
    for(int i = 0; i < N; i++){
        cin >> apex >> to;
        while(to != -1){
            cin >> wei;
            tree[apex].push_back({to, wei});
            cin >> to;
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    input();
    
    // 지름을 이루는 첫 번째 노드 찾기
    dfs(1, 0);
    max_dist = 0;
    memset(visited, 0, sizeof(visited));
    
    // 지름을 이루는 두 번째 노드 찾고 지름 구하기
    dfs(farthest_leaf, 0);
    
    cout << max_dist;
    
    return 0;
}