[코테] 백준 11438번 : LCA 2 (java)

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

알고리즘 분류 : 자료 구조, 트리, 최소 공통 조상, 희소 배열

❓문제

---

🔅해석

순서

1. input된 값을 adjacent list(양방향 간선)에 넣는다.
2. BFS로 트리 탐색
   • bfs로 트리를 탐색하면서 각 노드의 깊이(depth)와 부모(parent)를 기록한다. 
3. 희소 테이블(Sparse Table) 구성
   • 각 노드에 대해 2^k번째 부모를 미리 계산한다. 이 테이블을 이용하면, 두 노드의 깊이를 맞춘 후, 공통 조상을 빠르게 찾을 수 있다.
4. Find LCA
   
   1. 항상 b가 a보다 depth가 큰 노드(root로부터 먼)가 되도록 swap
   2. a, b의 depth 맞추기(0.에 의해 항상 b를 끌어올리게 된다)
   3. 2에서 depth를 맞추었는데 a와 b가 같다면 lca를 찾은 것
   4. a와 b를 같이 끌어올리면서 처음으로 조상이 같지 않은 지점(parent[0][a] != parent[0][b]) 까지 이동
   5. 4에서 2^0=1 에서 끝났으므로 a, b의 바로 위 조상이 lca가 된다

 

* Sparse Table 이란

특정 범위 내에서 최소값(깊이가 가장 작은 값)을 효율적으로 찾기 위해 사용된다.

각 노드에 대해 2^k번째 부모를 미리 계산한다. (보통 k(log)는 17로 설정한다.)

Sparse Table

 

---

⭕정답 코드

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

public class Main {

	static int LOG = 17;
	static int N, M;
	static ArrayList<Integer>[] adjList;

	static int[] depth;
	static boolean[] visited;
	static int[][] parent;
	static Queue<Integer> que = new LinkedList<>();
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());

		adjList = new ArrayList[N + 1];
		for (int n = 1; n <= N; n++) {
			adjList[n] = new ArrayList<>();
		}

		int n1, n2;
		for (int n = 0; n < N - 1; n++) {
			st = new StringTokenizer(br.readLine());
			n1 = Integer.parseInt(st.nextToken());
			n2 = Integer.parseInt(st.nextToken());
			adjList[n2].add(n1);
			adjList[n1].add(n2);
		}

		depth = new int[N + 1];
		visited = new boolean[N + 1];
		parent = new int[LOG + 1][N + 1];

		makeSpaseTable(1);

		setSpaseTable();

		// M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력
		M = Integer.parseInt(br.readLine());
		for (int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			n1 = Integer.parseInt(st.nextToken());
			n2 = Integer.parseInt(st.nextToken());

			sb.append(lca(n1, n2)).append("\n");
		}

		System.out.println(sb.toString());
		br.close();
	}

	private static int lca(int a, int b) {
		// 0. 항상 b가 a보다 depth가 큰 노드(root로부터 먼)가 되도록 swap
		if (depth[a] > depth[b]) {
			int temp = b;
			b = a;
			a = temp;
		}

		// 1. a, b의 depth 맞추기(0.에 의해 항상 b를 끌어올리게 된다)
		for (int k = LOG; k >= 0; k--) {
			int diff = depth[b] - depth[a];

			if (diff == 0)
				break;

			if (diff >= (1 << k)) {
				b = parent[k][b];
			}
		}

		// 2. 1.에서 depth를 맞추었는데 a와 b가 같다면 lca를 찾은 것
		if (a == b)
			return a;

		// 3. a와 b를 같이 끌어올리면서 처음으로 조상이 같지 않은 지점(parent[0][a] != parent[0][b]) 까지 이동
		// a와 b의 조상이 같으면 k--
		// a와 b의 조상이 같지 않으면 a와 b를 2^k 만큼 끌어올림
		for (int k = LOG; k >= 0; k--) {
			if (parent[k][a] != parent[k][b]) {
				a = parent[k][a];
				b = parent[k][b];
			}
		}
		// 4. 3.이 2^0=1 에서 끝났으므로 a, b의 바로 위 조상이 lca가 된다
		return parent[0][a];
	}

	private static void setSpaseTable() {
		for (int k = 1; k <= LOG; k++) {
			for (int v = 1; v <= N; v++) {
				parent[k][v] = parent[k - 1][parent[k - 1][v]];
			}
		}
	}

	private static void makeSpaseTable(int root) {
		que.offer(root);
		depth[root] = 0;
		parent[0][root] = 0;
		visited[root] = true;

		while (!que.isEmpty()) {

			int curNode = que.poll();

			for (int nextNode : adjList[curNode]) {
				if (!visited[nextNode]) {
					visited[nextNode] = true;

					parent[0][nextNode] = curNode;
					depth[nextNode] = depth[curNode] + 1;
					que.add(nextNode);
				}
			}
		}
	}
}

 

---

❗결과