[백준] 1167번 트리의 지름

1167 트리의 지름

문제

---

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

---

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다)

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

---

첫째 줄에 트리의 지름을 출력한다.

---

풀이)

단순하게 생각했다가 틀렸던 문제이다.

처음에

트리는 모두 연결되어있으니깐 

임의의 정점에서 거리가 먼 다른 정점까지의 거리를 구하면 된다고 생각했다.

하지만 반례가 존재했다.

한번의 계산으로는 구할 수 없었다.

//https://www.acmicpc.net/board/view/584

반례 input

7

1 2 1 3 1 -1

2 1 1 -1

3 1 1 4 3 5 2 -1

4 3 3 -1

5 3 2 6 3 7 10 -1

6 5 3 -1

7 5 10 -1

임의의 정점에서 가장 먼 정점을 구하고, 또 그 정점에서 가장 먼 정점을 구해서 그 거리를 출력해야한다.

코드)

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

#include <stdio.h> #include <vector> #include <queue> using namespace std; #define INF 1000000001 int V; vector<pair<int,int>> adj[100001]; int visited[100001];   pair<int,int> find_v(int s) {// s정점에서 가장 먼 정점과 그 거리 찾기          for (int i = 1; i <= V; i++) visited[i] = -1;     visited[s] = 0;     queue<pair<int,int>> qu;     qu.push({s,0});     while (!qu.empty())     {         int here = qu.front().first;         int cost = qu.front().second;         qu.pop();         for (int i = 0; i < adj[here].size(); i++) {             int next = adj[here][i].first;             int next_cost = cost + adj[here][i].second;             if (visited[next] != -1) continue;             visited[next] = next_cost;             qu.push({ next,next_cost });         }         }          int vertex = 0;     int temp = 0;     for (int i = 1; i <= V; i++) {         if (temp < visited[i]) {             vertex = i;             temp = visited[i];         }      }     return {vertex,temp}; } int main() {     scanf("%d", &V);     for (int i = 0; i < V; i++) {         int start =0, end=0, dist=0;         scanf("%d", &start);         while (true)         {             scanf("%d", &end);             if (end == -1) break;             scanf("%d", &dist);             adj[start].push_back({ end,dist });         }     }       //임의 정점에서 가장 먼 정점과 그 거리     pair<int, int> num = find_v(1);     //첫번째로 찾았던 가장 먼 정점에서 그 정점과 또 가장 먼 정점과 거리     pair<int, int> num2 = find_v(num.first);     printf("%d", num.second < num2.second? num2.second : num.second);     return 0; } Colored by Color Scripter

cs

+ 코드에서는 첫번째로 구한 먼 정점의 거리와 두번째로 구한 먼 정점의 거리를 비교해 더 큰 거리를 출력하는데 그럴 필요없다

   그냥 두번째로 구한 정점의 거리를 바로 출력하면 된다.