[1967번] 트리의 지름

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. '트리의 지름'에 대한 이해

2. dfs

3. bfs

트리의 지름에 대한 발상은

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

위의 내용을 이용하여 생각하였다.

위의 블로그에는 dfs를 통한 트리의 지름을 알아내는 방식이 존재하고,

아래 소스 코드에는 위의 내용을 기반으로 bfs를 통한 트리의 지름을 알아내는 방식을 만들었다.

   

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
typedef pair<int, int> pii;
vector<pii> vc[10002];
queue<int> q;
 
bool visit[10002];
int sum[10002];
int sMax, sPos;
 
void bfs(int pos)
{
    q.push(pos);
 
    while (!q.empty())
    {
        int here = q.front();
 
        visit[here] = 1;
        q.pop();
 
        for (int i = 0; i < vc[here].size(); i++)
        {
            // 방문하려고 하는 노드가 아직 방문하지 않은 경우
            if (visit[vc[here].at(i).first] == 0)
            {
                // 큐에 노드를 넣어준다.
                q.push(vc[here].at(i).first);
 
                // 해당하는 노드의 sum은 가중치 + 부모 노드의 누적합 
                sum[vc[here].at(i).first] += vc[here].at(i).second + sum[here];
 
                // 해당하는 노드의 sum이 최대인지 확인한다.
                if (sum[vc[here].at(i).first] > sMax)
                {
                    sMax = sum[vc[here].at(i).first];
                    sPos = vc[here].at(i).first;
                }
            }
        }
    }
}
 
int main()
{
    int n;
    int from, to, val;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d %d %d", &from, &to, &val);
 
        vc[from].push_back(pii(to, val));
        vc[to].push_back(pii(from, val));
    }
 
    // 1에서 부터 가장 멀리 있는 노드 탐색
    bfs(1);
 
    // 초기화
    fill(visit, visit + 10002, 0);
    fill(sum, sum + 10002, 0);
    sMax = 0;
 
    // 가장 멀리 있는 노드를 루트 노드로 하여 가장 멀리 있는 노드 탐색
    bfs(sPos);
 
    cout << sMax;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>