[백준] 1761 정점들의 거리
1761번: 정점들의 거리
첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩
www.acmicpc.net
2020-12-20
|
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main1761 {
public static class Node {
int y;
int v;
public Node(int y, int v) {
this.y = y;
this.v = v;
}
}
public static int N, M, dp[][], depth[], dist[];
public static List<List<Node>> list;
public static boolean vtd[];
public static int maxlevel = 16;
public static void dfs(int cur, int parent) {
vtd[cur] = true;
depth[cur] = depth[parent] + 1;
for(Node next: list.get(cur)) {
if(!vtd[next.y]) {
vtd[next.y] = true;
dp[next.y][0] = cur;
dist[next.y] = dist[cur] + next.v;
// dist[cur][next.y] = next.v;
// dist[parent][next.y] = dist[parent][cur] + dist[cur][next.y];
dfs(next.y, cur);
}
}
}
public static void solve() {
for(int y = 1; y <= maxlevel; y++) {
for(int x = 1; x <= N; x++) {
dp[x][y] = dp[dp[x][y-1]][y-1];
}
}
}
public static int lca(int x, int y) {
//x를 더 깊은 depth로 가정
if(depth[x] < depth[y]) {
int tmp = y;
y = x;
x = tmp;
}
for(int i = maxlevel; i >= 0; i--) {
if(Math.pow(2, i) <= depth[x] - depth[y]) {
x = dp[x][i];
}
}
if(x == y) return x;
else {
for(int i = maxlevel; i >= 0; i--) {
if(dp[x][i] != dp[y][i]) {
x = dp[x][i];
y = dp[y][i];
}
}
x = dp[x][0];
}
return x;
}
public static void main(String[] args) throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine().trim());
N = Integer.parseInt(st.nextToken());
list = new ArrayList<>();
vtd = new boolean[N+1];
dp = new int[N+1][maxlevel+1];
depth = new int[N+1];
// dist = new int[N+1][N+1];
dist = new int[N+1];
for(int i = 0; i <= N; i++) list.add(new ArrayList<>());
for(int i = 0; i < N-1; i++) {
st = new StringTokenizer(bf.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
list.get(x).add(new Node(y,v));
list.get(y).add(new Node(x,v));
}
dfs(1, 0);
solve();
st = new StringTokenizer(bf.readLine().trim());
M = Integer.parseInt(st.nextToken());
for(int i = 0; i < M; i++) {
st = new StringTokenizer(bf.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int res = lca(x, y);
System.out.println(dist[x] + dist[y] - 2*dist[res]);
}
}
}
|
cs |
[백준] 11437, 11438 LCA (2)
www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수
void2017.tistory.com
#문제풀이
1. 기존 LCA + 정점사이의 거리 계산이 필요한 문제이다. LCA 코드는 기존에 했던 방식과 동일하게 풀었다.
2. 정점계산을 처음에는 위에 주석처리를 한 것처럼 2차원 배열로 계산을 하였다. dist[x][y]를 만들어서, x는 lca값 y는 찾고자 하는 정점으로 계산을 하였다. 답은 맞았지만 제출을 하면 메모리초과가 나왔다.
3. 다른 방법이 딱히 생각이 나지 않아서 다른 블로그들을 참조해봤다. dist를 1차원 배열로 만들고, dist[x]값은 1부터~노드x까지의 합이다. 그래서 x, y사이의 거리를 구할 때는 dist[x] + dist[y] 를 한 후 2*dist[lca(x,y)] 중복되는 값을 빼주었다.
예를 들어 루트가 1이고 5,7 정점 사이의 거리를 구해야 할 때, lca(5,7)이 3인 경우가 있다고 가정해본다. 그러면 dist[5] 는 1부터 5까지의 거리이고, dist[7]은 1부터 7까지의 거리이다. 이 때, lca(5,7)의 값인 3의 정점도 2번 지나가게 된다. 그래서 dist[3] (1부터 3까지의 거리)에 2를 곱한 값을 빼주면된다.