출처 : 백준
문제 보러가기 : 트리의 지름
해당 문제를 해결하기 위해서는 우선 트리의 지름을 구하는 법을 알아야 한다.
트리의 지름은 두 노드 사이의 거리 중 최대 값을 말한다.
트리의 지름 구하기
1. 임의의 노드 1개를 기준으로 가장 먼 거리의 노드 X를 찾는다.2. 노드 X에서 가장 먼 거리의 노드까지의 거리를 구한다.
가장 먼 거리를 탐색하기 위해 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
|
#include <iostream>
#include <vector>
using namespace std;
int maxval = 0;
int maxnode;
vector<pair<int, int>> tree[100001];
int visit[100001];
void dfs(int current, int dist)
{
visit[current] = 1;
if (maxval < dist)
{
maxval = dist;
maxnode = current;
}
for (int i = 0; i < tree[current].size(); i++)
{
if (visit[tree[current][i].first] == 0)
{
dfs(tree[current][i].first, dist + tree[current][i].second);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int v, d, n, t;
cin >> v;
for (int i = 0; i < v; i++)
{
cin >> t;
while (1)
{
cin >> d;
if (d == -1)
break;
cin >> n;
tree[t].push_back({d, n});
}
}
dfs(1, 0);
for (int i = 0; i <= 100000; i++)
{
visit[i] = 0;
}
dfs(maxnode, 0);
cout << maxval << "\n";
return 0;
}
|
cs |
댓글