(백준) 1967 – 나무 지름(C++)

문제

1967: 나무의 지름(acmicpc.net)

설명

DFS를 한 번만 실행하면 이 문제를 해결할 수 없습니다.

먼저 주어진 그래프에서 가장 먼 지점을 찾는 DFS(start_node)와 이 start_node에서 가장 먼 지점(end_note)을 찾는 DFS를 총 두 번 반복해야 한다.

원의 가장 먼 점과 반대편의 가장 먼 점을 연결하면 지름이 되는 것처럼 그래프도 가장 먼 두 점을 찾아야 합니다.

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

vector<pair<int, int>> graph(10001);
bool visited(10001);
int start_node = 0;
int end_node = 0;

void dfs(int point, int length) {
    if (visited(point)) return;
    visited(point) = true;
    
    if (end_node < length) {
        end_node = length;
        start_node = point;
    }
    
    for (int i = 0; i < graph(point).size(); i++) {
      dfs(graph(point)(i).first, length + graph(point)(i).second);
    }
}

int main() {
    int n;
    cin >> n;
  
    for (int i = 0; i < n - 1; i++) {
        int parent, child, length;
        cin >> parent >> child >> length;
        
        // 양방향 모두 연결
        graph(parent).push_back({child, length});
        graph(child).push_back({parent, length});
    }
    
    // 일단 가장 멀리 떨어져 있는 곳(start_node) 구하기
    dfs(1, 0);
    end_node = 0;
    
    // 한번 갔으면 visited는 초기화 해줘야 한다
    memset(visited, 0, sizeof(visited));
    
    // start_node와 가장 멀리 떨어져 있는 곳(end_node) 구하기
    dfs(start_node, 0);
    cout << end_node;
    
    return 0;
}