1167 트리의 지름
알고리즘 (dfs, dp)
1
2
3
4
5
6
1. 1번 노드를 최상위 노드라고 가정하고 품
2. 1번 노드부터 시작하여 트리를 밑으로 탐색함.
3. 끝까지 닿으면, 거리를 올리면서(bottom-top) 다시 위로 올라감(재귀로 탐색하면 됨)
4. 한 노드에서 재귀로 반환하는 건, 자신의 자식 노드에서 올라오는 것중 가장 큰 값(끝까지 갔을 때의 값들 중 가장 큰 값)
5. 또 한 노드에선, 자식 노드에서 올라오는 것 중 가장 큰 값 2개를 저장하여, 탐색이 끝나면, 그 두개의 합이 전역으로 저장되어있는 length값보다 크면 저장.
6. 탐색이 모두 끝나면, 전역 length에 트리의 지름이 저장되어있음
코드
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> point[100001];
int N, maxLength;
bool check[100001];
long long getLength(int cur);
long long max(long long a, long long b) {
return a > b ? a : b;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
int cur, a, b;
cin >> cur;
cin >> a;
while (a != -1) {
cin >> b;
point[cur].push_back({ a, b });
cin >> a;
}
}
getLength(1);
cout << maxLength;
}
long long getLength(int cur) {
check[cur] = true;
bool isLast = true;
long long result[2] = { 0, 0 };
for (int i = 0; i < point[cur].size(); i++) {
if (!check[point[cur][i].first]) {
long long tmp = getLength(point[cur][i].first) + point[cur][i].second;
result[1] = max(result[1], tmp);
if (result[1] > result[0]) {
tmp = result[0];
result[0] = result[1];
result[1] = tmp;
}
isLast = false;
}
}
if (isLast)
return 0;
else {
maxLength =max(maxLength, result[0] + result[1]);
return max(result[0], result[1]);
}
}