백준알고리즘 1167번, 트리의 지름

트리의 지름은 두 vertex간의 길이가 가장 긴 값입니다. 이 문제에서는 간선에 가중치가 있기 때문에 멀어도 길이가 짧은 수 있고 그 반대가 될 수도 있습니다. 트리의 지름을 구하는 방법은

임의의 정점으로 부터 가장 먼 정점을 구한다.
1에서 나온 정점으로 부터 가장 먼 정점을 구한다.
1과 2에서 나온 정점간의 거리가 트리의 지름!

이 방법은 공식처럼 외우시면 됩니다. 증명은 구글링 하시면 잘 나옵니다.

저는 큐를 이용해 BFS로 풀었습니다. 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
88
89
90


#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
#include <utility>

using namespace std;

typedef pair<int, int> P; //노드, 거리

int main(void) {
 int V, u, v, w;
 vector<P> adj[100001];
 bool visited[100001] = { false };
 int cost[100001] = { 0 };
 queue<int> q;
 int curr, next, weight, max_weight=0,max_node;

#ifndef ONLINE_JUDGE
 freopen("input.txt", "r", stdin);
 freopen("output.txt", "w", stdout);
#endif

 scanf("%d\n", &V);
 for (int i = 0; i < V; i++) {
  scanf("%d", &u);
  do
  {
   scanf("%d", &v);
   if (v != -1) {
    scanf("%d", &w);
    adj[u].push_back(P(v, w));
   }

  } while (v!=-1);  
 }

 q.push(1); //1번 노드를 기준으로 BFS
 while (!q.empty()) {
  curr = q.front();
  q.pop();
  visited[curr] = true;
  for (int i = 0; i < adj[curr].size(); i++) {
   next = adj[curr][i].first;
   if (visited[next] == false) {
    weight = adj[curr][i].second;
    cost[next] = cost[curr] + weight;
    if (cost[next] > max_weight) {
     max_weight = cost[next];
     max_node = next;
    }
    q.push(next);
   }
  }
 }

 memset(visited, 0, sizeof visited);
 memset(cost, 0, sizeof cost);

 q.push(max_node); // 위의 BFS수행에서 나온 노드를 바탕으로 한번더 수행
 while (!q.empty()) {
  curr = q.front();
  q.pop();
  visited[curr] = true;
  for (int i = 0; i < adj[curr].size(); i++) {
   next = adj[curr][i].first;
   if (visited[next] == false) {
    weight = adj[curr][i].second;
    cost[next] = cost[curr] + weight;
    if (cost[next] > max_weight) {
     max_weight = cost[next];
     max_node = next;
    }
    q.push(next);
   }
  }
 }

 printf("%d\n", max_weight);


#ifndef ONLINE_JUDGE
 fclose(stdin);
 fclose(stdout);
#endif

 return 0;

}

Contents