[1167번] 트리의 지름

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 트리

2. bfs

이 문제는 [1967번] 트리의 지름 :: http://www.crocus.co.kr/586 문제 해설과 동일하다.

바뀐점은 int main의 입력 방식이 바뀐 것 및 배열의 크기만 바뀌었다.

첫 bfs를 통해 1에서 가장 멀리있는 노드를 구하고

두번째 bfs를 통해 가장 멀리있는 노드에서 가장 멀리있는 노드를 구하면 정답을 도출 할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87

#include <iostream> #include <cstdio> #include <vector> #include <queue>   using namespace std;   typedef pair<int, int> pii; vector<pii> vc[100002]; queue<int> q;   bool visit[100002]; int sum[100002]; 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; i++)     {         scanf("%d", &from);         while (1)         {             scanf("%d", &to);             if (to == -1)                 break;               scanf("%d", &val);             vc[from].push_back(pii(to, val));         }     }       // 1에서 부터 가장 멀리 있는 노드 탐색     bfs(1);       // 초기화     fill(visit, visit + 100002, 0);     fill(sum, sum + 100002, 0);     sMax = 0;       // 가장 멀리 있는 노드를 루트 노드로 하여 가장 멀리 있는 노드 탐색     bfs(sPos);       cout << sMax;       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus