[Algorithm/C++17] 백준 1967 트리의 지름

문제

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

1967번: 트리의 지름

풀이 방법

사이클이 없는 무방향 그래프에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당겼을 때, 가장 길게 늘어나는 경우가 있을 것이다. 이때 트리의 모든 노드들은 이 두 노드를 끝점으로 하는 원 안에 들어가게 되는데, 이런 두 노드 사이의 경로를 트리의 지름이라고 한다. (정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이)

 

이러한 트리의 지름을 구하는 문제다. 구하는 방법은 다음과 같다.

1. 트리에서 임의의 정점 x을 잡는다.
2. 정점 x에서 가장 먼 정점 y를 찾는다.
3. 정점 y에서 가장 먼 정점 z를 찾는다.
4. 정점 y와 정점 z를 연결하는 경로가 트리의 지름이다.

코드

#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
void dfs(vector<vector<pair<int,int>>>& v, vector<bool>& visited, vector<int>& dist, int cur)
{
    visited[cur] = true;
    for(auto& p : v[cur])
    {
        int next = p.first;
        int weight = p.second;
        if(visited[next]) continue;
        dist[next] = dist[cur] + weight;
        dfs(v, visited, dist, next);
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    vector<vector<pair<int,int>>> v(n+1, vector<pair<int,int>>());
    vector<bool> visited(n+1, false);
    vector<int> dist(n+1, 0);
    for(int i=0; i<n-1; i++)
    {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        v[a].push_back({b,w});
        v[b].push_back({a,w});
    }
    // 1. 트리에서 임의의 정점 x을 잡는다. (여기에서는 정점 1)
	// 2. 정점 x에서 가장 먼 정점 y를 찾는다.
    dfs(v, visited, dist, 1);
    int max_dist=-1, farthest;
    for(int i=1; i<=n; i++)
    {
        if(max_dist < dist[i])
        {
            max_dist = dist[i];
            farthest = i;
        }
    }
    fill(visited.begin(), visited.end(), false);
    fill(dist.begin(), dist.end(), 0);
    // 3. 정점 y에서 가장 먼 정점 z를 찾는다.
    dfs(v, visited, dist, farthest);
    // 4. 정점 y와 정점 z를 연결하는 경로가 트리의 지름이다.
    max_dist = -1;
    for(int i=1; i<=n; i++)
    {
        if(max_dist < dist[i])
        {
            max_dist = dist[i];
            farthest = i;
        }
    }
    printf("%d", dist[farthest]);
    return 0;
}

고찰

혼자 생각해서 O(N)에 풀기엔 좀 어려웠던 문제. 증명은 이 블로그에 자세히 나와있다.

트리의 지름 구하기

또한 이 문제도 유사한 방법으로 풀 수 있다.