문제 풀이

[백준] 1167번 트리의 지름

컴영 2020. 8. 18. 21:24

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;
}
cs


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

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

저작자표시 비영리 변경금지