![[백준] 11437 LCA , 11438 LCA2 (자바 Java)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FZWCvI%2FbtrSBoBIcyA%2FfVpQVLua74tzjDyUj6KA2k%2Fimg.png)
[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)으로 구하는 방법을 통해 풀어야 한다.
LCA(Lowest Common Ancestor) 알고리즘
LCA(Lowest Common Ancestor) 알고리즘이란? LCA 알고리즘이란 영어 해석 그대로 최소 공통 조상을 찾는 알고리즘이고, 두 정점 u, v(혹은 a, b)에서 가장 가까운 공통 조상을 찾는 과정을 말한다. 예를들어
www.crocus.co.kr
위 사이트를 참고해서 혼자 이해해보려고 하였다.
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 |