백준 1167번: 트리의 지름 (C++)

 

문제 링크 : www.acmicpc.net/problem/1167

 

 

 

tip) 임의의 한 점에서 제일 먼 점은 반드시 지름의 양 끝 점 중에 하나라는 사실만 생각해내면 된다.

 

 

<전체적인 알고리즘>

1. 임의의 한 점에서 제일 먼 점을 찾는다. (지름의 끝 점 중 하나를 찾는다)

2. 그 점으로 부터 제일 먼 점까지의 거리를 구한다 

 

   -> 제일 먼 점을 찾는건 bfs 나 dfs로 구한다.

 

 

 

 

<전체 코드>

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

#include<iostream> #include<vector> #include<algorithm> #include<queue>   using namespace std;   vector<pair<int, int>> a[100002]; bool check[100002]; int max_cost = 0; int result = 0;   int find_corner(int start) {     queue<pair<int, int>> q;     q.push(make_pair(start, 0));     check[start] = true;     max_cost = 0;     int corner = 0;       while (!q.empty())     {         int node = q.front().first;         int cost = q.front().second;         q.pop();           if (max_cost < cost)         {             corner = node;             max_cost = cost;         }           for (int i = 0; i < a[node].size(); i++)         {             int next = a[node][i].first;             int edge = a[node][i].second;             if (check[next])continue;             check[next] = true;             q.push(make_pair(next,cost+edge));         }     }     return corner; }     int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);       int n;     cin >> n;           for (int i = 0; i < n; i++ )     {         int n1;         cin >> n1;         while (1)         {             int n2, edge;             cin >> n2;             if (n2 == -1)break;             cin >> edge;             a[n1].push_back(make_pair(n2, edge));             a[n2].push_back(make_pair(n1, edge));         }     }       int corner= find_corner(1);   //제일 구석탱이 node 찾기 (지름의 끝점 중 한 점)     fill(&check[0], &check[100001], 0);     find_corner(corner);   //나머지 끝점까지의 거리 구하기     cout << max_cost;     return 0; }

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.