[백준/BOJ] 1167번 트리의 지름 (C++)

www.acmicpc.net/problem/1167

1167번: 트리의 지름

트리 유형의 문제 (다시 풀기)

트리에서의 지름이란 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다고 합니다. 지름을 구하는 유명한 공식(?)이 있다는 것을 처음으로 알게 되었는 데, 트리에서 지름을 구하는 방법은 다음과 같습니다.

 

1. 트리에서 임의의 정점 v1을 잡는다.

2. 정점 v1에서 가장 먼 정점 v2를 찾는다.

3. 정점 v2에서 가장 먼 정점 v3를 찾는다.

 

정점 v2와 v3를 연결하면 트리의 지름이 된다.

 

이러한 공식이 어떻게 성립할 수 있는지를 보여주는 증명은 다음 블로그를 참고하였습니다.

 

www.weeklyps.com/entry/%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84

트리의 지름

blog.myungwoo.kr/112

트리의 지름 구하기

 

#include <iostream>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        #include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int n, target, diameter = -2147000000;
vector<pair<int, int > > tree[100001];
bool visit[100001];

void DFS(int node, int sum) {
    visit[node] = true;
    
    if(diameter < sum) {
        diameter = sum;
        target = node;
    }
    
    for(int i = 0; i < tree[node].size(); i++) {
        int next = tree[node][i].first;
        int nextVal = tree[node][i].second;
        if(!visit[next]) DFS(next, sum + nextVal);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        int v1, v2, e;
        cin >> v1;
        while(1) {
            cin >> v2;
            if(v2 == -1) break;
            cin >> e;
            tree[v1].push_back({ v2, e });
        }
    }
    
    // 임의의 한 정점에서 가장 먼 정점까지 거리 구하기
    DFS(1, 0);
    memset(visit, false, sizeof(visit));
    // 방금 구한 target에서 가장 먼 정점까지 거리 구하기
    DFS(target, 0);
    
    cout<<diameter;
}