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

문제

백준 1967 트리의 지름 C++

1967번: 트리의 지름

풀이

dfs를 사용합니다.

1. 1이 항상 루트 노드이므로, 1에서 가장 먼 노드를 찾습니다.

2. 가장 먼 노드에서 다시 dfs를 실행하여, 다른 가장 먼 노드 까지의 거리를 구합니다.

3. 그 거리가 트리의 지름이 됩니다. 트리의 지름을 출력합니다.

소스 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
struct node
{
    // 정점 번호
    int vertex;
    // 가는 거리
    int dist;
};
 
vector<node> v[10001];
bool visited[10001];
int n, maxnode, maxdist;
 
void dfs(int cur, int dist) {
    if (visited[cur])
        return;
    visited[cur] = true;
    // 거리 갱신
    if (dist > maxdist) {
        maxdist = dist;
        maxnode = cur;
    }
    for (int i = 0; i < v[cur].size(); i++) {
        int next = v[cur][i].vertex;
        int nextdist = v[cur][i].dist + dist;
        dfs(next, nextdist);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    // 입력
    cin >> n;
    int a, b, d;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b >> d;
        v[a].push_back({ b, d });
        v[b].push_back({ a, d });
    }
    // 시작 지점에서 가장 먼 정점 찾기
    dfs(1, 0);
    memset(visited, 0, sizeof(visited));
    maxdist = 0;
    // 가장 먼 정점에서 다른 가장 먼 정점 찾기
    dfs(maxnode, 0);
    cout << maxdist;
    return 0;
}