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

1967번: 트리의 지름

노드 간의 가장 긴 거리를 구하는 문제이다. dfs를 사용했다. 먼저 경로들을 벡터에 양방향으로 저장을 해주고 노드의 갯수만큼 반복문을 돌려주었다. dfs 함수에서 경로를 따라 sum을 구해 res와 비교 후 더 큰 값을 저장해주었다. 최종적으로 모든 노드를 돌게되면서 가장 큰 값이 저장되게되고 이를 출력하였다.
간선을 저장하는 아이디어는 이전에 다익스트라 문제를 풀 때 이용했던 방식을 사용했다. 시간 초과가 날 줄 알았는데 바로 통과해서 빠르게 풀 수 있었다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int n, res = 0;
bool check[10001];
vector<pair<int, int>> v[10001];

void dfs(int depth, int cur, int sum) {
    res = max(res, sum);

    for (int i = 0; i < v[cur].size(); i++) {
        int next = v[cur][i].first;
        int cost = v[cur][i].second;

        if (check[next]) continue;

        check[next] = true;
        dfs(depth + 1, next, sum + cost);
    }
}

void solution() {
    for (int i = 0; i < n; i++) {
        memset(check, 0, sizeof(check));
        check[i] = true;
        dfs(0, i, 0);
    }

    cout << res;
}

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

    cin >> n;

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

    solution();

    return 0;
}