[Platinum V] LCA 2 - 11438
성능 요약
메모리: 101548 KB, 시간: 996 ms
분류
자료 구조(data_structures), 최소 공통 조상(lca), 희소 배열(sparse_table), 트리(trees)
문제 설명
N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.
두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.
입력
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.
출력
M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.
풀이(LCA)
최소 공통 조상에 대해서는 처음 알아서 공부하면서 풀었다.
11437 LCA의 경우는 n이 크지 않아서 dp를 사용하지 않고도 풀 수 있었다.
핵심은 두 노드의 깊이를 같게 해준 후에, 공통 조상이 나올 때까지 부모를 찾는 과정을 반복하는 것이었다.
부모를 찾는 과정은 dfs를 통해서 찾고, 그 과정에서 노드의 깊이 (rank)를 기록하였다.
static void dfs(int curr, int p) {
rank[curr] = rank[p] + 1;
parent[curr] = p;
for (int i = 0; i < adjList[curr].size(); i++) {
int child = adjList[curr].get(i);
if (rank[child] == 0 && child != p) {
dfs(child, curr);
}
}
}
LCA를 구할 때에는 먼저 두 노드의 깊이를 같게 해준 후에 공통 조상이 나올 때까지 부모를 찾으면 된다.
private static void LCA(BufferedReader br) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int rankA = rank[start];
int rankB = rank[end];
if (rankA != rankB) {
while (rankA > rankB) {
rankA--;
start = parent[start];
}
while (rankB > rankA) {
rankB--;
end = parent[end];
}
}
while (start!=end) {
start=parent[start];
end=parent[end];
}
sb.append(start).append("\n");
}
전체 코드
package BOJ.Gold.g3;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class BOJ_11437_LCA {
static int N, M;
static List<Integer>[] adjList;
static int[] rank;
static int[] parent;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
adjList = new ArrayList[N + 1];
for (int i = 1; i <= N; i++)
adjList[i] = new ArrayList<>();
rank = new int[N + 1];
parent = new int[N + 1];
for (int i = 0; i < N - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
adjList[start].add(end);
adjList[end].add(start);
}
dfs(1, 0);
M = Integer.parseInt(br.readLine());
for (int i = 0; i<M; i++) {
LCA(br);
}
System.out.print(sb);
}
private static void LCA(BufferedReader br) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int rankA = rank[start];
int rankB = rank[end];
if (rankA != rankB) {
while (rankA > rankB) {
rankA--;
start = parent[start];
}
while (rankB > rankA) {
rankB--;
end = parent[end];
}
}
while (start!=end) {
start=parent[start];
end=parent[end];
}
sb.append(start).append("\n");
}
static void dfs(int curr, int p) {
rank[curr] = rank[p] + 1;
parent[curr] = p;
for (int i = 0; i < adjList[curr].size(); i++) {
int child = adjList[curr].get(i);
if (rank[child] == 0 && child != p) {
dfs(child, curr);
}
}
}
}
풀이 (LCA 2)
LCA2는 N이 커져서 LCA1의 알고리즘 (O(n))으로는 시간 안에 답을 구할 수 없다.
N이 최대 10만, LCA를 구하기 위한 쌍이 최대 10만이기 때문에 100억 연산을 초과한다.
그래서 dp를 이용하여 O(logN)으로 구하는 방법을 통해 풀어야 한다.
위 사이트를 참고해서 혼자 이해해보려고 하였다.
15의 조상은 차례대로 11, 5, 2, 1이다.
2의 k승에 해당하는 조상만 찾는다면 $2^0$ 번째 조상=11, $2^1$ 번째 조상=5, $2^2$ 번째 조상은 1이다.
15의 $2^0$ 번째 조상인 11을 기준으로 찾으면 $2^0$ 번째 조상=5, $2^1$ 번째 조상=2가 된다.
즉 원소 i에 대해 i의 2^k번째 조상은 i의 2^k-1번째 조상의 k-1번째 조상과 같다.
$$ dp[i][k] = dp[dp[i][k-1][k-1] $$
점화식은 다음과 같다.
이렇게 트리의 높이만큼 2^k번째 부모까지 dp에 기록해두면, 깊이를 맞춰주고 LCA를 찾는 과정이 O(logN)으로 줄게 된다.
처음에는 이 과정에서 2^k에 해당하지 않는 부모는 어떻게 계산할 수 있는건지 헷갈렸는데, 높이를 맞춰주는 과정에서 모든 경우의 수를 탐색할 수 있게 된다.
예를 들어 x의 깊이가 10, y의 깊이가 4라면 x의 깊이를 4에 맞춰주어야 한다.
x의 $2^3$ 번째 조상의 깊이는 10-8=2이다. 2는 4보다 작으니 무시하고 다음 값을 찾는다.
x의 $2^2$ 번째 조상은 10-4=6이다. 6은 4보다 크거나 같기 때문에 x의 조상으로 x 값을 업데이트한다.
다시 x(깊이=6)의 $2^1$ 번째 조상의 깊이는 4가 된다. y의 깊이와 같기 때문에 업데이트하고 여기서 멈춘다.
x를 새로운 값(x의 조상)으로 업데이트한 후에 다시 max_depth부터 검사하지 않는 이유는 이미 x가 max_depth부터 검사했기 때문에 해당 범위는 검사할 필요가 없기 때문이다.
LCA를 구하는 과정을 코드로 보면 다음과 같다.
private static void LCA(BufferedReader br) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
// A가 깊이가 더 깊은 애로 맞춰주기
if (rank[start] < rank[end]) {
int tmp = start;
start = end;
end = tmp;
}
// 두 노드의 깊이가 같아질 때까지 2^k번
for (int i = maxLevel; i >= 0; i--) {
if (Math.pow(2, i) <= rank[start] - rank[end])
start = parent[start][i];
}
// 두 노드가 같아졌다면
if (start == end) {
sb.append(start).append("\n");
return;
}
// 높이는 같지만, 부모가 같지 않을 경우 같은 부모를 찾아서 ㄱㄱ
for (int i = maxLevel; i >= 0; i--) {
if (parent[start][i] != parent[end][i]) { // 두 노드의 부모가 같은 노드의 직전까지 감
start = parent[start][i];
end = parent[end][i];
}
}
sb.append(parent[start][0]).append("\n");
}
먼저 start를 깊이가 더 긴 노드로 두기 위해 필요한 경우 두 값을 swap한다.
이때 maxLevel은 트리의 최대 깊이로 N개의 노드의 경우 ((int) logN)+1과 같다.
maxLevel부터 값을 줄여나가며 두 노드의 깊이가 같아질 때까지 start를 update한다.
깊이를 같게 해준 후에 두 값이 같다면 그 값이 최소공통조상이므로 출력한다.
두 값이 같지 않다면 최소공통조상을 찾아야 한다. maxLevel부터 다시 값을 줄여나가면서 두 노드의 i번째 부모가 같지 않다면 값을 업데이트한다.
이 과정을 반복하다보면 최소공통조상의 바로 전 단계까지 값이 업데이트될 것이다.
이 사진에서 4와 6의 공통조상을 구한다고 가정하면, 2^1번째 조상은 1로 같으므로 start와 end를 업데이트하지 않는다.
2^0번째 조상도 2로 같으므로 업데이트하지 않는다.
0까지 검사가 끝났으므로 두 노드의 2^0번째 조상인 2가 최소공통조상이 된다.
다른 예시로 4와 8의 공통조상을 구한다고 가정해보자.
4와 8의 2^1번째 조상은 1로 같으므로 업데이트하지 않는다.
4와 8의 2^0번째 조상은 2와 3으로 다르기 때문에 start를 2, end를 3으로 업데이트한다.
0까지 검사가 끝났으므로 2와 3의 조상인 1이 최소공통조상이 된다.
트리를 하나하나 그려서 케이스별로 생각해보니 이해할 수 있었다.
package BOJ.Platinum.p5;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class BOJ_11438_LCA2 {
static int N, M;
static List<Integer>[] adjList;
static int[] rank;
static int[][] parent;
static StringBuilder sb = new StringBuilder();
static int maxLevel;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
adjList = new ArrayList[N + 1];
for (int i = 1; i <= N; i++)
adjList[i] = new ArrayList<>();
rank = new int[N + 1];
int tmp = 100000;
maxLevel = 1;
while (tmp > 1) {
tmp /= 2;
maxLevel++;
} // logN
parent = new int[N + 1][maxLevel + 1];
for (int i = 0; i < N - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
adjList[start].add(end);
adjList[end].add(start);
}
dfs(1, 0);
findParent();
M = Integer.parseInt(br.readLine());
for (int i = 0; i < M; i++) {
LCA(br);
}
System.out.print(sb);
}
private static void findParent() {
for (int i = 1; i <= maxLevel; i++)
for (int j = 1; j <= N; j++) {
parent[j][i] = parent[parent[j][i - 1]][i - 1]; // j의 2^j번째 조상 = j의 2^i-1번째 조상의 2^i-1번째 조상
}
}
private static void LCA(BufferedReader br) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
// A가 깊이가 더 깊은 애로 맞춰주기
if (rank[start] < rank[end]) {
int tmp = start;
start = end;
end = tmp;
}
// 두 노드의 깊이가 같아질 때까지 2^k번
for (int i = maxLevel; i >= 0; i--) {
if (Math.pow(2, i) <= rank[start] - rank[end])
start = parent[start][i];
}
// 두 노드가 같아졌다면
if (start == end) {
sb.append(start).append("\n");
return;
}
// 높이는 같지만, 부모가 같지 않을 경우 같은 부모를 찾아서 ㄱㄱ
for (int i = maxLevel; i >= 0; i--) {
if (parent[start][i] != parent[end][i]) { // 두 노드의 부모가 같은 노드의 직전까지 감
start = parent[start][i];
end = parent[end][i];
}
}
sb.append(parent[start][0]).append("\n");
}
static void dfs(int curr, int p) {
rank[curr] = rank[p] + 1;
parent[curr][0] = p;
for (int i = 0; i < adjList[curr].size(); i++) {
int child = adjList[curr].get(i);
if (rank[child] == 0 && child != p) {
dfs(child, curr);
}
}
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 2343 - 기타 레슨 (자바 Java) (0) | 2022.12.03 |
---|---|
[백준] 1654 - 랜선 자르기 (자바 Java) (1) | 2022.12.02 |
[백준] 2042 - 구간 합 구하기 (자바 Java) : 세그먼트 트리 (0) | 2022.11.29 |
[백준] 19237 - 어른 상어 (자바 Java) (0) | 2022.11.28 |
[백준] 10942 - 팰린드롬? (자바 Java) (0) | 2022.11.27 |