[백준] 1967: 트리의 지름

0. 문제 주소

 

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

1967번: 트리의 지름

 

 

1. 풀이

 

1. 아무 점 u에서 가장 먼 거리에 있는 점 v를 구한다.

 

2. 점 v에서 가장 먼 거리에 있는 점 w를 구한다.

 

3. 이 때 v와 w 사이의 거리가 트리의 지름이 된다.

 

 

증명은 아래 두 링크를 참고했다.

 

https://www.weeklyps.com/entry/%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84

트리의 지름

 

https://blog.myungwoo.kr/112

트리의 지름 구하기

 

 

 

2. 풀이 코드

 

* 유의할 점

 

 

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

#define pii pair<int, int>
#define MAX 10005

using namespace std;

int N;
vector<pii> graph[MAX];
int dist[MAX];
bool visited[MAX];

void dfs(int curr){
    visited[curr] = true;
    for (auto p: graph[curr]){
        int next = p.first, weight = p.second;
        if (visited[next]) continue;
        dist[next] = dist[curr] + weight;
        dfs(next);
    }
    return;
}


int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d", &N);
    int u, v, w;
    for (int i=0;i<N-1;i++){
        scanf("%d %d %d", &u, &v, &w);
        graph[u].push_back(pii(v, w));
        graph[v].push_back(pii(u, w));
    }
    
    dfs(1);
    
    int S, max_dist = -1;
    for (int i=1;i<=N;i++){
        if (max_dist < dist[i]){
            max_dist = dist[i];
            S = i;
        }
    }
    
    memset(visited, 0, sizeof(visited));
    memset(dist, 0, sizeof(dist));
    
    dfs(S);
    
    int ans = *max_element(dist+1, dist+N+1);
    printf("%d\n", ans);

    return 0;
}