🔺 문제
11438번: LCA 2
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
🔺 코드
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
114
115
116
117
|
import java.util.*;
import java.io.*;
public class Main {
static int N, M, K;
static int[] depth;
static int[][] parent;
static ArrayList<Integer>[] tree;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
// 2^K > N 인 K 찾기
K = 0;
for(int i = 1 ; i <= N ; i *= 2) {
K++;
}
// LCA 관련 변수 초기화
depth = new int[N + 1];
parent = new int[K][N + 1];
// tree 관련 변수 초기화
tree = new ArrayList[N + 1];
for(int i = 1 ; i <= N ; i++) {
tree[i] = new ArrayList<>();
}
for(int i = 1 ; i < N ; i++) {
st = new StringTokenizer(br.readLine()," ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
tree[s].add(e);
tree[e].add(s);
}
// depth 확인
DFS(1, 1);
// 2^N까지 parent 채우기
fillParent();
// LCA 진행
M = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < M ; i++) {
st = new StringTokenizer(br.readLine()," ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
sb.append(LCA(s, e) + "\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
// depth 확인용 DFS
static void DFS(int node, int cnt) {
depth[node] = cnt;
for(int next : tree[node]) {
if(depth[next] == 0) {
DFS(next, cnt + 1); parent[0][next] = node; // 첫번째 부모 기록
}
}
}
// 부모 채우기 (2^k번째 조상 노드 저장)
static void fillParent() {
for(int i = 1 ; i < K ; i++) {
for(int j = 1 ; j <= N ; j++) {
parent[i][j] = parent[i-1][parent[i-1][j]];
}
}
}
// 최소 공통 조상
static int LCA(int a, int b) {
// 1. depth[a] >= depth[b]가 되도록 조정
if(depth[a] < depth[b]) {
int tmp = a;
a = b;
b = tmp;
}
// 2. 더 깊은 a를 2^K승 점프해 depth !빠르게! 맞추기
for(int i = K - 1 ; i >= 0 ; i--) {
if(Math.pow(2, i) <= depth[a] - depth[b]) {
a = parent[i][a];
}
}
// 3. depth를 맞췄는데 같다면 종료
if(a == b) return a;
// 4. a,b는 같은 depth이므로 2^K승 점프해 공통부모 바로 아래까지 올리기
for(int i = K - 1 ; i >= 0 ; i--) {
if(parent[i][a] != parent[i][b]) {
a = parent[i][a];
b = parent[i][b];
}
}
return parent[0][a];
}
}
|
cs |
✅ 해결 아이디어
✔ LCA 빠르게 구하기! 점화식 이용
→ P[K][N] = P[K-1][P[K-1][N]]
과정
1) 인접 리스트로 트리 데이터 구현
2) 각 노드 깊이 계산 (탐색 알고리즘 사용)
3) 부모 노드 배열 구하기 (점화식 사용)
4) 깊이가 큰 노드는 부모 노드 배열 이용해 2^K만큼 이동시켜 깊이 맞춤
5) 부모 노드로 올라가면서 LCA 찾기 (2^K만큼 넘어가면서 찾기! K는 depth 최댓값에서 -1씩 하면서)
💥 유의사항
• 최소 공통 조상 로직 ⇨ LCA 2^N 이용 & DP적 요소
🔺 다른 풀이들
다들 비슷한데 parent 배열에서 i와 j의 자리를 바꿔 쓰셨다.
[JAVA/백준] 11438번: LCA 2
PS & 개발 기록
iamheesoo.github.io
그리고 2^K > N
인 최초의 K를 찾을 때 비트 시프트 연산자 <<를 사용하셨다.
int maxDepth = 0;
int K = 1;
// 트리의 깊이 계산
while(K <= N) {
K <<= 1;
maxDepth++;
}
💬 느낀 점
뭔지는 알겠는데 혼자 하라면 아직은 못 할 것 같아서 복습을 해야겠다!
깊이가 안 맞을 때 한 칸씩 올라가는 게 아니라 2의 제곱수씩 올라가서 빠른 LCA라고 하는 것이라함!!
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
[BOJ 백준] LCA 2(11438) Java
링크 : https://www.acmicpc.net/problem/11438 문제 설명 : 더보기 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두
subbak2.com
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1010번: 다리 놓기 (0) | 2023.05.10 |
---|---|
[백준/JAVA] 11051번: 이항 계수 2 (0) | 2023.05.10 |
[백준/JAVA] 11437번: LCA (0) | 2023.05.10 |
[백준/JAVA] 11505번: 구간 곱 구하기 (0) | 2023.05.09 |
[백준/JAVA] 10868번: 최솟값 (0) | 2023.05.09 |