BOJ 1967 - 트리의 지름

BOJ 1967 - 트리의 지름

“트리의 지름 구해보기”

BOJ 1967 - 트리의 지름

문제 링크


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

int N;
long long node, ans;
vector<pair<int,int>> adj[10010];
bool    vis[10010];

void    dfs(int k, int dist)
{
    if (vis[k])
        return ;

    vis[k] = 1;

    if (dist > ans) {
        ans = dist;
        node = k;
    }

    for (int i = 0; i < adj[k].size(); i++)
        dfs(adj[k][i].first, dist + adj[k][i].second);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;

    if (N == 1) {
        cout << 0; return 0;
    }

    for (int i = 0; i < N; i++) {
        int p, c, w; cin>>p>>c>>w;
        adj[p].push_back({c, w});
        adj[c].push_back({p, w});
    }

    dfs(1, 0);
    ans = 0;
    for (int i = 0; i <= 10001; i++) 
        vis[i] = 0;
    dfs(node, 0);
    cout << ans;
    return 0;
}

  • 트리의 지름에 대한 기본적인 속성은 문제에 제시되어있다. 하지만 트리의 지름을 구하는 요령을 모르면 푸는데 상당히 애를 먹을 것 같다.

  • dfs를 두 번 도는 것으로 트리의 가장 긴 지름의 길이를 구할 수가 있다. 구글 선생님에 따르면, 어떠한 정점으로부터 가장 멀리 떨어진 정점은 반드시 트리의 지름 부분에 있는 정점이고, 트리의 지름 부분에 있는 정점으로부터 가장 멀리 떨어진 정점과의 길이를 구하면 그것이 바로 트리의 지름이다.

  • 나는 평소에 인접 행렬을 사용해서 문제를 푸는 것에 익숙해있었는데, 이 문제의 경우 노드가 10000개까지 들어올 수 있는데다가, 가중치까지 기록해야해서 인접 행렬을 쓰기가 까다로웠다. 이 문제를 풀면서 인접 리스트의 사용법에 대해서도 익혔는데, pair로 구성된 벡터(vector<pair<int,int>> adj)를 쓰면 정점과 가중치를 쉽게 기록할 수 있고, 인접 행렬과 달리 for 문을 순회하는 횟수가 적어서 편리하다는 점을 알게 되었다(벡터에 포함된 정점만 순회하면 된다).