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

[ 문제 ]

 

1167번: 트리의 지름 (acmicpc.net)

 

[ 접근방법 ]

 

크게 3단계를 거친다.

 

1. 아무데서나 DFS를 시작하여 거리가 가장 먼 점 X을 구한다.

2. 위에서 구한 점에서 다시 DFS를 시작하여 거리가 가장 먼 점 Y를 구한다.

3. X, Y 사이의 거리가 트리의 지름이다.

 

만약 X가 지름에 속해있다면 XY는 지름이 자명하다.

 

만약 X가 지름에 속해있지 않다고 가정해보자.

시작점을 A라고 하며, 지름의 양 끝점을 U, V라고 하자.

상황 그림

 

트리의 특성상 AX와 UV는 무조건 교차하는 점이 존재한다. 이 점을 T라고 하자.

UV = UT + TV이고, UV는 트리 내에서 제일 길기에 TX < TV가 성립한다.

그러면 AX < AT + TV가 되기에 조건에 모순이 된다.

 

따라서 위의 3단계를 거치면 무조건 트리의 지름을 구할 수 있다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>

using namespace std;

int v, a, b, c, maxSum, maxVertex;

vector<pair<int, int>> edge[100005];

bool chk[100005];

void dfs(int x, int sum)
{
    if (sum > maxSum)
    {
        maxSum = sum;
        maxVertex = x;
    }

    chk[x] = true;

    for (auto i : edge[x])
        if (!chk[i.first])
            dfs(i.first, sum + i.second);

    chk[x] = false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> v;
    for (int i = 0; i < v; i++)
    {
        cin >> a;
        while (1)
        {
            cin >> b;
            if (b == -1)
                break;
            cin >> c;
            edge[a].push_back({b, c});
        }
    }

    for (int i = 1; i <= v; i++)
        chk[i] = false;
    dfs(1, 0);
    for (int i = 1; i <= v; i++)
        chk[i] = false;
    dfs(maxVertex, 0);

    cout << maxSum;

    return 0;
}