백준 | 11438번. LCA 2 - 최소 공통 조상 문풀

⬛ 백준 11438번. LCA 2 - 최소공통조상 문풀

https://www.acmicpc.net/problem/11438

11438번: LCA 2

문제

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

---

💚 문제 접근 방식

→ 이 문제는 11437번의 데이터 크기보다 (노드 개수, M개의 질의 개수) 모두 커진 문제이다.

→ 따라서 조금 더 최적화하여 (제곱근 형태 이용한 빠르게 LCA 구하는 방식)으로 풀어야 한다.

→ 또한, Scanner 보다 BufferReader를 활용하여 입력값을 받아서 시간을 더 줄였다.

1) 데이터 초기화 하기

• a) tree는 인접 리스트로 구현하여 양방향 간선 정보로 이어준다.
• b) kmax를 구한다. (N개 데이터에 대한 최대 높이 2^k 만족하는 kmax)
• c) BFS나 DFS 탐색하며 2^0 즉, 1칸 위의 부모노드와 깊이를 초기화해준다.
• d) k=1~kmax까지 모든 노드들에 대한 2^k 씩 점프해서 닿는 부모 노드를 DP 활용하여 구해준다.

→ parent[k][n] : n번 노드의 2^k 번째 위 부모노드 지칭 parent[k][n] = parent[k-1][parent[k-1][n] ] 를 이중 for문 돌면서 갱신해준다.

2) 데이터 질의 처리하기

• M개의 질의에 대해서 getLCA(a,b)로 두 노드의 LCA 출력해준다,

getLCA(a,b){
  //1) 깊이 더 큰 노드가 b가 되도록 swap 처리

  //2) 깊이 더 큰 b 가 a와 깊이 같아지도록 두 노드 깊이 차이만틈 거슬러 올라감
	for(int k=kmax; k>=0; k--){
		if(Math.pow(2,k) <= depth[b] - depth[a]) {
			if(depth[a] <= depth[ parent[k][b]] ) { //b의 2^k점프한 부모의 깊이가 a 보다 작거나 같은 경우에만 
				b = parent[k][b]; //거슬러올라감 

	//3) 깊이 같아진 상황에서 a,b 동시에 올림
	for(int k = kmax; k>=0; k--){
		//거슬러 올라가도 두 노드 부모 다를 때까지 쭉 올림 
		if(parent[k][a] != parent[k][b]){
			a = parent[k][a];
			b = parent[k][b];

    int LCA = a;
    if(a != b) {
        //즉, 둘이 다른 경우 바로 윗칸이 부모 노드가 됨 
        LCA = parent[0][LCA];
    return a;
}

---

💚 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 11438번. LCA2 - 최소 공통 조상 문풀 
 * @author MYLG
 *
 */
public class Main {
	static ArrayList<ArrayList<Integer>> tree;
	static int[] depth;
	static int kmax; //kmax
	static int[][] parent;
	static boolean[] visited;
	//BFS
	private static void BFS(int root) {
		Queue<Integer> Q = new LinkedList<>();
		Q.offer(root);
		visited[root] = true;
		
		while(!Q.isEmpty()) {
			int cur = Q.poll();
			for(int nx : tree.get(cur)) {
				if(!visited[nx]) {
					visited[nx] = true;
					Q.offer(nx);
					//세팅
					parent[0][nx] = cur;
					depth[nx] = depth[cur]+ 1;
				}
			}
		}
	}
	
	//getLCA
	private static int getLCA(int a, int b) {
		//더 큰 쪽을 b로 swap 처리 
		if(depth[a] > depth[b]) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		//두 노드의 깊이를 2^k 씩 거슬러 올려줌 
		for(int k=kmax; k>=0; k--) {
			//두 노드의 깊이 차이에 맞는 최대 k에 대해서 (점프용)
			if(Math.pow(2, k) <= depth[b]-depth[a]) {
				if(depth[a] <= depth[parent[k][b]]) {
					//b 깊이가 더 크기 때문에 a에 맞춰주기 위해 
					b = parent[k][b];//계속 부모로 거슬러 올라감 
				}
			}
		}
		//같은 깊이에서 LCA 찾기 
		for(int k=kmax; k>=0; k--) { //역순 순회하면서 
			//a의 2^k 부모와 b의 2^k 부모 다르다면 계속 거슬러 올려줌 
			if(parent[k][a] != parent[k][b]) {
				a = parent[k][a];
				b = parent[k][b];
			}
		}
		
		int LCA = a;
		if(a != b) {
			LCA = parent[0][LCA];//바로 위에 꺼가 LCA임
		}
		return LCA;
	}
	
	
	//실행 메인 
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		tree = new ArrayList<>();
		for(int i=0; i<= N; i++) tree.add(new ArrayList<>());
		
		//1) 데이터 초기화 하기 
		//kmax 구해줘야 됨 = treeHeight
		int len = N;
		kmax = 0;
		
		while(len != 0) {
			len/=2;
			kmax++;
		}
		
		depth = new int[N+1];
		parent = new int[kmax+1][N+1];//N+1개의 노드들 각각에 대한 2^k번쨰 위의 부모 저장
		visited = new boolean[N+1];
	
		//데이터 저장
		for(int i=0; i<N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			//양방향 간선임
			tree.get(a).add(b);
			tree.get(b).add(a);
		}
		
		BFS(1);//각 노드의 한칸 위 부모노드, 깊이 세팅 세팅 
		
		//2) getLCA로 두 노드의 LCA 구하기 
		for(int k=1; k<=kmax; k++) { //kmax까지 하나씩 늘려보면서 더블점프 부모 세팅  
			for(int n = 1; n<=N; n++) { //모든 노드들에 대해서
				parent[k][n] = parent[k-1][parent[k-1][n]];
			}
		}
		
		//질의 처리 개수
		int M = Integer.parseInt(br.readLine());
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			System.out.println(getLCA(a, b));
		}	
	}
}