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

문제

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

1967번: 트리의 지름

생각

처음에는 노드 들을 다 순회해서 끝 노드까지의 거리 중 가장 큰 2가지가 지름이다. 라는 방식으로 접근을 했다.

풀면서 계속 꼬여서 결국에 다른 살마의 코드를 참고했다.

1번 노드부터 시작을 해서 dfs로 탐색을 하여 거리가 1번 노드로부터 가장 먼 노드를 구한다.

이후 가장 먼 노드부터 시작을 해서 같은 dfs로 탐색을 하여 가장 거리가 먼 노드와의 거리가 곧 지름이 된다.

코드

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

//끝점을 찾은 후 거기서 다시 DFS

int n;
vector<pair<int, int>> tree[10001];
int vst[10001];
int diameter = 0;
int farNode = 0;

void dfs(int node, int cost) {
    if(vst[node]) return;
    vst[node] = true;

    if(cost > diameter) {
        diameter = cost;
        farNode = node;
    }

    for(int i = 0; i < tree[node].size(); i++) {
        int destination = tree[node][i].first;
        int nxtCost = tree[node][i].second;
        dfs(destination, cost + nxtCost);
    }
    return;
}

int main() {
    cin >> n;
    for(int i = 0; i < n - 1; i++) {
        int start, destination, cost;
        cin >> start >> destination >> cost;
        tree[start].push_back({destination , cost});
        tree[destination].push_back({start, cost});
    }
    memset(vst, false, sizeof(vst));
    dfs(1, 0);
    //farthest node 찾음
    memset(vst, false, sizeof(vst));
    diameter = 0;
    dfs(farNode, 0);
    cout << diameter;
}