BOJ 1967 : 트리의 지름 [C++]

문제

1967번: 트리의 지름

 

 

이전에 풀었던 문제와 같은 방식의 문제였고, 재수강 중인 자료구조 강의의 오늘자 과제와 유사해서 금방 푼 문제.

BOJ 1167 : 트리의 지름 [C++]

 

 

루트에서 dfs 한번, 그리고 루트에서 최대 거리가 나오는 노드에서 dfs 한번 더.

 

#include <iostream>
#include <vector>

std::vector<std::pair<int, int>> edges[10001];
bool visited[10001] = {false, };
int max_dist = 0;
int max_node = 0;

void dfs(int start, int dist) {
    visited[start] = true;

    if (dist > max_dist) {
        max_dist = dist;
        max_node = start;
    }

    for (int i = 0; i < edges[start].size(); i++) {
        if (visited[edges[start][i].first]) {
            continue;
        }
        dfs(edges[start][i].first, dist + edges[start][i].second);
    }
}

int main() {
    int n = 0;
    std::cin >> n;

    for (int i = 0; i < n - 1; i++) {
        int parent = 0, child = 0, weight = 0;
        std::cin >> parent >> child >> weight;
        edges[parent].push_back({child, weight});
        edges[child].push_back({parent, weight});
    }

    dfs(1, 0);

    for (int i = 1; i < n + 1; i++) {
        visited[i] = false;
    }

    dfs(max_node, 0);

    std::cout << max_dist << "\n";

    return 0;
}