[ 백준 1167 ] 트리의 지름 (c/c++)

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

 

 

[ 문제 요약 ]

트리에서 임의 두 점 사이 거리의 최대값을 트리의 지름이라고 할 때 트리의 지름을 출력한다.

 

 

[ 문제 풀이 ]

1. 임의의 하나의 점에서 출발을 했을 때 DFS를 통해서 임의의 점에 대한 최대값을 구할 수 있다.

2. 임의의 점에 대한 최대값의 노드는 트리의 지름의 점 중 하나가 된다.

3. 임의의 점에서 다시 최대값을 구하게 되면 트리의 지름을 구할 수 있다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, node;
int visited[101010];
vector<pair<int, int>> v[101010];
long long max_dist;

void DFS(int n, int dist){
    if (visited[n]) return;
    if (max_dist < dist){
        max_dist = dist; node = n;
    }
    visited[n] = 1;
    for (int i = 0; i<v[n].size(); i++){
        int x = v[n][i].first;
        int y = v[n][i].second;
        DFS(x, y + dist);
    }
}

int main() {
    cin >> N;
    for (int i=0; i<N; i++){
        int num, a, b;
        cin >> num >> a;
        while (a != -1){
            cin >> b;
            v[num].push_back(make_pair(a, b));
            cin >> a;
        }
    }

    DFS(1, 0);
    fill(visited, visited + 101010, 0);
    max_dist = 0;
    DFS(node, 0);
    cout << max_dist;
    
    return 0;
}

 

 

 

[ 주의할 점 ]

DFS를 한 번 시행했을 때 가장 먼 거리의 노드가 트리의 지름의 하나의 점이 된다는 것을 이해하면 쉽게 구할 수 있다.