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

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

 

#include <iostream>
#include <vector>
using namespace std;

vector<vector<pair<int, int>>> g;
vector<bool> vst;
int maxc = 0;

void dfs(int cur, int cnt) {
    vst[cur] = true;
    if (cnt > maxc) maxc = cnt;
    for (auto nxt: g[cur]) {
        if (!vst[nxt.first]) dfs(nxt.first, cnt + nxt.second);
    }
}

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

    int n;
    cin >> n;
    g = vector<vector<pair<int, int>>>(n + 1);

    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }

    for (int i = 1; i < n + 1; i++) {
        vst = vector<bool>(n + 1, false);
        dfs(i, 0);
    }

    cout << maxc << '\n';
}

오랜만에 푸는 듯한 dfs 문제... 각 노드에 대해서 전부 dfs를 실행시키면서 maxc를 갱신시키면 되는 간단한 문제였다. 주의할 점은 각 노드별로 dfs 실행할 때마다 vst를 초기화해야 한다는 것이다. (AC)