반응형
문제
https://www.acmicpc.net/problem/1167
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되
www.acmicpc.net
풀이
트리에서 지름은 거리가 가장 먼 두 점 사이를 의미한다. 이를 구하기 위해 먼저 임의의 노드에서 가장 거리가 먼 노드를 구한다. 그 다음 방금 구한 가장 거리가 먼 노드를 기준으로 해서 다시 한번 가장 거리가 먼 노드를 구한다. 그러면 두 개의 노드가 구해지게 되고, 이 두 노드 사이의 거리는 가장 멀게 되므로 트리의 지름을 알 수 있게 된다.
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
|
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int V;
vector< pair<int, int> > graph[100001];
bool visit[100001];
int result;
int farNode;
void dfs(int x, int sum)
{
visit[x] = true;
if (result < sum)
{
result = sum;
farNode = x;
}
for (int i=0; i<graph[x].size(); i++)
{
int next = graph[x][i].first;
int weight = graph[x][i].second;
if (!visit[next]) dfs(next, sum + weight);
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(0);
cin >> V;
int from, to, weight;
for (int i=0; i<V; i++)
{
cin >> from;
while (true)
{
cin >> to;
if (to == -1) break;
cin >> weight;
graph[from].push_back({to, weight});
}
}
dfs(1, 0);
memset(visit, 0, sizeof(visit));
dfs(farNode, 0);
cout << result;
return 0;
}
|
cs |
반응형
'BOJ' 카테고리의 다른 글
백준 1753 - 최단경로 (1) | 2020.01.10 |
---|---|
백준 1197 - 최소 스패닝 트리 (0) | 2019.12.26 |
백준 1744 - 수 묶기 (0) | 2019.10.09 |
백준 1697 - 숨바꼭질 (0) | 2019.10.02 |
백준 2875 - 대회 or 인턴 (0) | 2019.09.30 |