[BOJ] 1167. 트리의 지름

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

1167번: 트리의 지름

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말합니다. 트리의 지름을 구하는 기본 알고리즘은 다음과 같습니다.

1. 임의의 한 노드 A를 선택합니다.
2. 노드 A에서 가장 먼 노드 B를 찾습니다.
3. 노드 B에서 가장 먼 노드 C를 찾습니다.
4. 노드 B와 노드 C 사이의 경로의 길이가 트리의 지름입니다.

더 긴 지름이 존재한다면 모순임을 보이면 증명됩니다.

코드는 다음과 같이 작성해 보았습니다.

#include <bits/stdc++.h>

using namespace std;

int v;
vector<pair<int, int>> tree[100001];
bool visited[100001];
pair<int, int> r = {1, 0};

void getFar(int i, int p)
{
    visited[i] = true;
    if (r.second < p)
        r = {i, p};
    for (auto [ii, pp] : tree[i])
    {
        if (visited[ii])
            continue;
        getFar(ii, p + pp);
    }
    visited[i] = false;
}

int main()
{
    cin >> v;
    for (int i = 0; i < v; i++)
    {
        int a, b = 0, c;
        cin >> a;
        while (b != -1)
        {
            cin >> b;
            if (b == -1)
                break;
            cin >> c;
            tree[a].push_back({b, c});
        }
    }
    getFar(1, 0);
    r.second = 0;
    getFar(r.first, 0);
    cout << r.second;
}

DFS를 두 번 이용하는 코드로, 첫 번째 DFS에서는 임의의 노드 (1번 노드)에서 가장 먼 노드를 찾아 r에 넣고, 해당 노드에서 다시 DFS를 돌려서 가장 먼 노드를 찾습니다. 이 때의 경로의 길이가 트리의 지름입니다.

관련 문제

[BOJ] 1967.트리의 지름

1967번: 트리의 지름