[백준] 1167 트리의 지름
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지
www.acmicpc.net
2020-11-22
|
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
|
javjajimport java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class Node {
int n;
int w;
Node(int n, int w){
this.n = n;
this.w = w;
}
}
public class Main1167 {
public static int N, answer, leaf;
public static boolean vtd[];
public static List<Node> list[];
public static void solve(int idx, int sum) {
vtd[idx] = true;
if(sum > answer) {
answer = Math.max(sum, answer);
leaf = idx;
}
for(Node node: list[idx]) {
if(!vtd[node.n]) {
solve(node.n, sum+node.w);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
list = new ArrayList[N];
vtd = new boolean[N];
for(int i = 0; i < N; i++) list[i] = new ArrayList();
for(int i = 0; i < N; i++) {
int p = sc.nextInt()-1;
while(true) {
int x = sc.nextInt()-1;
if(x == -2) break;
int w = sc.nextInt();
list[p].add(new Node(x, w));
}
}
//dfs (1)
answer = 0;
leaf = 0;
solve(0, 0);
//dfs (2)
answer = 0;
for(int i = 0; i < N; i++) vtd[i] = false;
solve(leaf, 0);
System.out.println(answer);
}
}
|
cs |
'트리의 지름' 이라는 개념이 잘 이해가 안되서 고민고민하다가 결국 검색해서 찾아봤다. 내가 이해한 바로는 임의의 두 점 사이의 거리가 가장 멀려면, 어떠한 임의의 정점에서 다른 정점까지 갈 때의 가중치의 합이 가장 커야한다. 이 때, 이 문제에서는 루트를 알 수가 없으니, 임의의 정점을 찾고 나서 다른 정점까지 계산을 해야만 한다.
1. 편의상 정점은 0부터 시작하게 하였다. 입력값을 받을 때, 부모 정점 기준으로 새로운 정점을 저장할 때 자식 정점과 가중치값을 저장하였다.
2. dfs는 두 번을 돌았다. 첫 번째 dfs에서 돌 때는 leaf 노드를 가장 깊숙히 있는 leaf 노드를 찾았다. 어떠한 정점을 시작점으로 잡아도 상관은 없지만, 편의상 0으로 시작하였다. 정점들을 탐색하면서 가중치의 합이 가장 크게 나올 때의 idx값을 leaf라는 변수에 저장하였다.
3. 두 번째 dfs를 돌 때는 (2)번에서 저장해뒀던 leaf라는 변수를 시작점으로 잡고, 탐색을 시작했다. (2)번과 마찬가지의 방법으로 탐색하면서 가장 가중치가 큰 값을 더했었다.
(+) 두 번째 dfs를 돌 때 가중치의 합이 자꾸 이상하게 나왔었다. 왜 그러지 정말 한참을 고민하다가 코드를 다시 뜯어봤는데, sum + node.w가 아니라 sum+=node.w 로 되어 있어서 그랬었다.....;
solve(node.n, sum+node.w);