https://www.acmicpc.net/problem/1167
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지
www.acmicpc.net
가장 긴 경로 찾기
임의의 노드에서 가장 긴 경로로
연결된 노드는 트리의 지름에 해당하는 두 노드 중 하나이다.
https://johoonday.tistory.com/217
백준 No.1167 [트리의 지름]
BOJ No.1167 [트리의 지름] 문제 1167번: 트리의 지름 (acmicpc.net) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V
johoonday.tistory.com
설령 (y) 정점가 (u) 정점, (v) 정점 과 겹치지 않더라도
(y) 정점가 포함된 지름의 길이는
(u) 정점, (v) 정점 으로 이루어진 지름의 길이와 같다.
이 아이디어만 있으면
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
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> edge;
vector<vector<edge>> arr;
vector<bool> visited;
vector<int> ans_dist;
void bfs(int idx)
{
queue<int> q;
q.push(idx);
visited[idx] = true;
while (!q.empty())
{
int now = q.front();
q.pop();
for (edge i : arr[now])
{
if (!visited[i.first])
{
visited[i.first] = true;
q.push(i.first);
//거리 배열 업데이트
ans_dist[i.first] = ans_dist[now] + i.second;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
arr.resize(n + 1);
for (int i = 0; i < n; i++)
{
int s;
cin >> s;
while (true)
{
int e, v;
cin >> e;
if (e == -1)
break;
cin >> v;
arr[s].push_back(edge(e, v));
}
}
ans_dist = vector<int>(n + 1, 0);
visited = vector<bool>(n + 1, false);
// 1에서 bfs 한 번 실행
bfs(1);
int dae = 1;
for (int i = 2; i <= n; i++)
{
// 1에서 bfs 했을 때
// 최대 지름을 구함
if (ans_dist[dae] < ans_dist[i])
dae = i;
}
fill(ans_dist.begin(), ans_dist.end(), 0);
fill(visited.begin(), visited.end(), false);
bfs(dae);
sort(ans_dist.begin(), ans_dist.end());
cout << ans_dist[n] << '\n';
}
|
cs |