백준 1967 트리의 지름 (C++)

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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<pair<int, int>> g[10001];



int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int ans = 0;
    cin >> n;




    for (int i = 0; i < n - 1; i++) {
        int u, v, d;
        cin >> u >> v >> d;

        g[u].push_back(make_pair(v, d));
        g[v].push_back(make_pair(u, d));


    }

    vector<int> leaf;

    for (int i = 1; i <= n; i++) {
        if (g[i].size() == 1) {
            leaf.push_back(i);
        }
    }


    for (int i = 0; i < leaf.size(); i++) {

        queue<int> q;
        vector<int> dist(n + 1, 0);
        vector<bool> visit(n + 1, false);

        q.push(leaf[i]);
        visit[leaf[i]] = true;

        while (!q.empty()) {

            int cur = q.front();
            int d = dist[cur];

            q.pop();

            if (cur != leaf[i] && g[cur].size() == 1) {
                ans = max(ans, d);
                continue;
            }


            for (int j = 0; j < g[cur].size(); j++) {
                if (!visit[g[cur][j].first]) {
                    visit[g[cur][j].first] = true;
                    dist[g[cur][j].first] = d + g[cur][j].second;
                    q.push(g[cur][j].first);
                }
            }

        }

    }



    cout << ans;

    return 0;
}

1. 문제

트리의 노드의 개수 n과 n-1개의 간선과 가중치가 주어진다. 루트 노드는 항상 1번 노드이고, 간선의 가중치는 100 이하의 자연수이다. 트리 중 가장 긴 경로의 길이를 트리의 지름이라 할 때, 이를 구하라.

2. 풀이

트리의 가중치가 양수이므로 트리의 지름을 나타내는 경로는 leaf to leaf 중 하나라 할 수 있다.

    vector<int> leaf;

    for (int i = 1; i <= n; i++) {
        if (g[i].size() == 1) {
            leaf.push_back(i);
        }
    }

트리 중 리프 노드를 배열에 집어넣는다.

for (int i = 0; i < leaf.size(); i++) {

        queue<int> q;
        vector<int> dist(n + 1, 0);
        vector<bool> visit(n + 1, false);

        q.push(leaf[i]);
        visit[leaf[i]] = true;

        while (!q.empty()) {

            int cur = q.front();
            int d = dist[cur];

            q.pop();

            if (cur != leaf[i] && g[cur].size() == 1) {
                ans = max(ans, d);
                continue;
            }


            for (int j = 0; j < g[cur].size(); j++) {
                if (!visit[g[cur][j].first]) {
                    visit[g[cur][j].first] = true;
                    dist[g[cur][j].first] = d + g[cur][j].second;
                    q.push(g[cur][j].first);
                }
            }

        }

    }

각 leaf에서 시작하여 BFS를 돌린다. 각 노드를 방문할 때 마다 해당 길이를 dist에 저장한다. 방문하였을 때 시작점이 아닌 leaf node라면 ans 변수에 거리의 최댓값을 갱신해준다.

 위 연산이 끝나고 이를 출력하면 정답을 구할 수 있다.