[백준 알고리즘]11438번: LCA 2_Java

[시간 제한]

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