1967번 트리의 지름

처음에는 BFS를 1 ~ 정점 끝까지 다 돌면서, 최댓값을 구하려고 했으나 생각해보니 너무 비효율적이었다.

그래서 다른 분의 글을 보았는데, 요약하자면

트리의 지름은 우선 아무 정점(여기에서 나는 편하게 root 노드로 잡았다.)에서 출발하여

가장 먼 곳에 있는 정점을 찾는다. 찾은 이 정점은 트리의 지름에 해당하는 두 정점 중 하나이다.

그러므로, 이 정점에서 다시 가장 먼 곳에 있는 정점을 찾으면 이 두 개의 정점이 트리의 지름에 해당한다.

이 문제는 '가중치'를 활용한 문제이다.

내가 참고한 글 2개

1. http://blog.sisobus.com/2013/10/backjoon-online-judge-no1967.html#.W7BSDWgzZPZ

2. http://blog.myungwoo.kr/112

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int N = 0;
 
vector<pair<int, int> > v[10001]; // child, weight
 
bool visit[10001] = { false, };
 
int V = 0, W = 0;
int sum[10001] = { 0, };;
 
void BFS(int start)
{
    memset(visit, false, sizeof(visit));
 
    queue<int> q;
 
    q.push(start);
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int here = q.front();
 
            q.pop();
 
            if (visit[here]) continue;
 
            visit[here] = true;
 
            for (int i=0; i<v[here].size(); i++)
            {
                int next_vertex = v[here].at(i).first;
 
                if (!visit[next_vertex])
                {
                    q.push(next_vertex);
 
                    sum[next_vertex] += v[here].at(i).second + sum[here];
 
                    if (W < sum[next_vertex])
                    {
                        W = sum[next_vertex];
                        V = next_vertex;
                    }
                }
            }
        }
    }
}
 
int main(void)
{
    int parent = 0, child = 0, weight = 0;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N - 1; i++)
    {
        scanf("%d %d %d", &parent, &child, &weight);
 
        v[parent].push_back({ child, weight });
        v[child].push_back({ parent, weight });
    }
 
    BFS(1);
 
    memset(sum, 0, sizeof(sum));
 
    BFS(V);
 
    printf("%d\n", W);
    
    return 0;
}