[시간 제한]
Java 8: 2.5 초
Java 8 (OpenJDK): 2.5 초
Java 11: 2.5 초
Kotlin (JVM): 2.5 초
[문제]
N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.
두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.
[입력]
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.
[출력]
M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.
[예제]
| 예제 입력1 | 예제 출력1 |
| 15 1 2 1 3 2 4 3 7 6 2 3 8 4 9 2 5 5 11 7 13 10 4 11 15 12 5 14 7 6 6 11 10 9 2 6 7 6 8 13 8 15 |
2 4 2 1 3 1 |
>문제 풀이
LCA: Lowest Common Ancestor
최소 공통 조상 알고리즘에 대한 문제입니다.
문제의 예제를 트리로 만들어 놓고 이 트리를 기준으로 LCA에 대해 설명을 하자면,
어떤 노드 u, v에 대해 depth가 더 깊은 노드를 조상노드로 올리고 올려 depth를 맞추고, 그 위에 공통으로 가지는 부모 노드를 찾는 것입니다.
말로 하는 것보다 그림으로 보는게 더 직관적으로 이해가 가기 때문에, 그림으로 살펴보겠습니다.
u와 v를 보면 depth가 같지 않습니다.
u를 v의 depth와 같아질 때까지 부모노드를 타고 올라갑니다.
그러면, parent[u]= 4 와 v를 비교하게 됩니다.
이 두 정점의 공통 부모는 2번째 노드가 되는걸 알 수 있습니다.
그럼 u와 v를 기준으로 한 층씩 올라가며 부모노드를 찾아주면 될까요??
문제에서는 N이 100,000 M이 100,000까지 들어올 수 있습니다.
만약 트리가 한쪽으로 치우치기라도 한다면 정점 u, v에 대해, 한번씩 부모 노드로 옮겨가며 lca를 찾게되는데, 최악의 경우 O(N)의 연산이 필요합니다.
그리고 M개의 케이스가 들어오면 O(M*N) 이 되어버려서 시간초과가 발생할 수 있습니다.
이를 해결하기 위해 탐색의 방법을 살펴봐야하고, dp로 정점 V에 대한 K번째 부모노드 값을 메모이제이션을 해줄 필요가 있습니다.
탐색의 시간을 줄이는 것은 어떻게 효과적으로 트리를 접어갈 수 있냐는 것입니다.
이 코드에서는 부모 노드를 나타내기 위해 parent [ ] [ ] 2차원 배열을 사용했습니다.
* parent[K][V]: 노드 V의 2^K번째 부모 노드의 번호
그리고 이 parent[i][j] 배열을 채워줘야 하는데, 아래의 표를 보면 알 수 있듯이
parent[i][j]= parent[i-1][parent[i-1][j]] 의 점화식이 성립합니다.
*** 로직 ***
1) 들어오는 두 정점의( u, v ) depth를 비교하기 위해
dfs로 depth를 구하여 depth[N+1] 배열에 담아주었습니다.
2) 2^K 점프를 통해 두 정점의 depth를 맞춰주고
더 깊은 depth를 가진 정점 u를 2^k점프하여 (depth[u]- depth[v]) 보다 작거나 같게 맞춰줍니다.
3) 공통 부모 바로 아래까지 올려줍니다.
그러면 정점 u와 v의 부모는 lca(최소 공통 부모) 니까
return parent[0][u];
>전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int N, M, K; //N:정점개수, M:TC개수, K
//LCA 관련 변수
static int[] depth;
static int[][] parent; // parent[K][V] 정점 V의 2^K번째 조상 정점 번호
// parent[K][V]= parent[K-1][parent[K-1][V]];
//Tree 변수
static ArrayList[] tree;
public static void main(String[] args) throws IOException {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
//1. 입력
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<Integer>();
}
int a, b;
for(int i=1; i<=N-1; i++) { //입력받고 트리 만들기
st= new StringTokenizer(br.readLine());
a= Integer.parseInt(st.nextToken());
b= Integer.parseInt(st.nextToken());
//양방향 간선
tree[a].add(b);
tree[b].add(a);
}
//2. Depth 확인
dfs(1, 1);
//3. 2^N 까지 parent 채우기
fillParent();
//4. LCA 진행
M= Integer.parseInt(br.readLine());
StringBuilder sb= new StringBuilder();
for(int i=1; i<=M; i++) {
st= new StringTokenizer(br.readLine());
a= Integer.parseInt(st.nextToken());
b= Integer.parseInt(st.nextToken());
sb.append(lca(a, b)+"\n");
}
System.out.println(sb.toString());
}// main
//Depth를 구함
public static void dfs(int node, int cnt) {
//1. depth를 기록
depth[node]= cnt;
//2. 자식들의 depth를 기록
int len= tree[node].size(); //자식 몇개인지
for(int i=0; i<len; i++) {
int next= (Integer)tree[node].get(i);
//아직 깊이를 모르면 -> 미방문 노드
if(depth[next]==0) {
dfs(next, cnt+1);
parent[0][next]= node; //next 노드의 2^0= 첫번째 부모를 기록
}
}
}
//부모 채우기
static void fillParent() {
for(int i=1; i<K; i++) {
for(int j=1; j<=N; j++) {
//j번 노드의 i번째 부모= j의 i-1번째 부모의 i-1번째 부모
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 temp=a;
a= b;
b= temp;
}
//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];
}//lca
}https://www.acmicpc.net/problem/11438
11438번: LCA 2
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
'알고리즘 > 백준 알고리즘' 카테고리의 다른 글
| [백준 알고리즘]2449번: 전구_Java (0) | 2021.09.30 |
|---|---|
| [백준 알고리즘]11659번: 구간 합 구하기4_Java (0) | 2021.09.30 |
| [백준 알고리즘]2042번: 구간 합 구하기_Java (0) | 2021.09.30 |
| [백준 알고리즘]1202번: 보석도둑_Java (0) | 2021.09.30 |
| [백준 알고리즘]1806번: 부분합_Java (0) | 2021.08.03 |
