백준 1167 - 트리의 지름

문제

 

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

1167번: 트리의 지름

 

 

풀이

 

트리에서 지름은 거리가 가장 먼 두 점 사이를 의미한다. 이를 구하기 위해 먼저 임의의 노드에서 가장 거리가 먼 노드를 구한다. 그 다음 방금 구한 가장 거리가 먼 노드를 기준으로 해서 다시 한번 가장 거리가 먼 노드를 구한다. 그러면 두 개의 노드가 구해지게 되고, 이 두 노드 사이의 거리는 가장 멀게 되므로 트리의 지름을 알 수 있게 된다.

 

dfs 탐색을 이용해서 노드와 거리를 구한다.

 

 

코드

 

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
int V;
vector< pair<int, int> > graph[100001];
bool visit[100001];
int result;
int farNode;
 
void dfs(int x, int sum)
{
    visit[x] = true;
 
    if (result < sum)
    {
        result = sum;
        farNode = x;
    }
 
    for (int i=0; i<graph[x].size(); i++)
    {
        int next = graph[x][i].first;
        int weight = graph[x][i].second;
        if (!visit[next]) dfs(next, sum + weight);
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> V;
 
    int from, to, weight;
 
    for (int i=0; i<V; i++)
    {
        cin >> from;
        while (true)
        {
            cin >> to;
            if (to == -1) break;
            cin >> weight;
            graph[from].push_back({to, weight});
        }
    }
 
    dfs(1, 0);
    memset(visit, 0, sizeof(visit));
    dfs(farNode, 0);
    
    cout << result;
 
    return 0;
}