[백준][BOJ11438] LCA2 (with. DFS)

1. 문제 : https://www.acmicpc.net/problem/11438

11438번: LCA 2

---

2. 풀이 : LCA + 오일러 투어 테크닉

---

3. 시간복잡도 : O(MlogN)

---

4. 설명

문제의 예시를 그림으로 표현하면 그림[1]과 같다.

그림[1]

루트(1번)에서부터 오일러 투어 테크닉을 사용하여 각 노드들의 진입/진출 순서를 확정한다. 

그림[2]

그림[2]에서 진입 순서 배열을 in이라고 하고 진출 순서 배열을 out이라고 하였을 때, 두 노드 a와 b에 대하여 다음이 성립한다.

1. in[a] <= in[b] && out[a] >= out[b] 라면 a는 b의 조상이다. (그림[3])

그림[3]

2. in[a] > in[b] || out[a] < out[b] 라면 a는 b의 조상이 아니다. (그림[4], 그림[5])

그림[4]

그림[5]

오일러 투어를 진행하며 그림[6]과 같이 각 노드들의 2^0번째 조상, 즉 부모 노드를 확정한다.

그림[6]

루트 노드의 부모인 '-1'값은 조상이 없음을 의미한다.

그림[7]

희소 배열을 sparse라고 했을 때, 아래의 식이 성립하며 그림[7]과 같이 각 노드의 나머지 조상 값들을 채워 넣을 수 있다.

sparse[a][n] = sparse[sparse[a][n-1]][n-1]

a와 b의 최소 공통 조상을 찾는 과정은 아래와 같다.

    1-1. a가 b의 조상이라면, a와 b의 최소 공통 조상은 a이므로 탐색을 종료한다.

    1-2. a가 b의 조상이 아니라면, n의 값을 가장 큰 값부터 0까지 1씩 줄여가며 a의 2^n번째 조상의 값이 나올 때까지 탐색한다.

    2-1. a의 2^n번째 조상이 b의 조상이라면 탐색을 재개한다.

    2-2. a의 2^n번째 조상이 b의 조상이 아니라면, a의 위치를 2^n번째 조상 노드로 변경하고, 변경된 a와 b의 최소 공통 조상을 탐색한다.

    3. n이 0이 되었을 때 탐색을 종료하며, 그때의 a의 부모 노드가 최소 공통 조상이 된다.

15(a)와 14(b)의 최소 공통 조상을 찾는 경우를 예시로 보자. n의 가장 큰 값부터 1씩 줄여가며 탐색을 했을 때, 15의 조상이 14의 조상이 안 되는 최초의 경우는 그림[8]과 같이 n이 1인 경우이다.

그림[8]

a의 위치를 15에서 5로 변경하고 탐색을 재개한다. 이때, n의 값은 0이며 5의 2^0번째 조상인 2 역시 14의 조상이 아니므로 a의 위치를 2로 변경한다.

그림[9]

n이 0일 때까지 탐색을 하였으므로, 탐색을 종료하며 이때 a의 위치는 그림[10]과 같다. 탐색이 종료되었을 때 sparse[a][0] 즉, sparse[2][0] 값이 15와 14의 최소 공통 조상이 되며 그 값은 1이다.

---

5. 코드

	package lca;
	import java.io.BufferedReader;
	import java.io.BufferedWriter;
	import java.io.File;
	import java.io.FileInputStream;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.io.OutputStreamWriter;
	import java.util.ArrayList;
	import java.util.List;
	import java.util.StringTokenizer;
	public class LCA2_DFS {
	private static int N;
	private static int M;
	private static List<Integer>[] input;
	private static int NN;
	private static int LIMIT;
	private static int[] in; //진입
	private static int[] out; //진출
	private static int count; //진입 or 진출 순서
	private static int[][] sparse; //희소 배열
	public static void main(String[] args) throws IOException {
	System.setIn(new FileInputStream(new File("LCA2")));
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	StringTokenizer st = null;
	N = Integer.parseInt(br.readLine());
	input = new List[N+1];
	for(int i=1; i<=N; i++) {
	input[i] = new ArrayList<Integer>();
	}
	NN = 1;
	LIMIT = 0;
	while(N > NN) {
	NN*=2;
	LIMIT++;
	}
	in = new int[N+1];
	out = new int[N+1];
	sparse = new int[N+1][LIMIT];
	for(int i=1; i<N; i++) {
	st = new StringTokenizer(br.readLine());
	int a = Integer.parseInt(st.nextToken());
	int b = Integer.parseInt(st.nextToken());
	input[a].add(b);
	input[b].add(a);
	}
	sparse[1][0] = -1; //루트의 2^0번째 조상은 없다.
	setOrder(1); //오일러 투어 테크닉, 각 노드의 2^0번째 조상 확정
	setSparse(); //각 노드들에 대하여 2^0번째 조상을 제외한 나머지 조상 확정
	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());
	int lca = lca(a, b); //a와 b의 최소 공통 조상
	bw.append(String.valueOf(lca)).append("\n");
	}
	bw.close();
	}
	private static int lca(int a, int b) {
	//b가 a의 자식 노드인 경우
	if(in[a] <= in[b] && out[a] >= out[b]) {
	return a; //최소 공통 조상은 a
	}
	int pos = LIMIT-1; //a의 2^(LIMIT-1)번째 조상부터 탐색
	while(pos >= 0) {
	int cur = sparse[a][pos];
	if(cur == -1) { //조상이 없는 경우
	pos--;
	continue;
	}
	/*
	* a의 2^pos번째 조상이 b의 조상이 아니라면 a를 a의 2^pos번째 조상으로 변경
	* a와 b의 최소 공통 조상 = a의 2^pos번째 조상과 b의 최소 공통 조상
	*/
	if(in[cur] > in[b] || out[cur] < out[b]) {
	a = cur;
	}
	pos--;
	}
	return sparse[a][0];
	}
	private static void setSparse() {
	for(int j=1; j<LIMIT; j++) {
	for(int i=1; i<=N; i++) {
	if(sparse[i][j-1] == -1) {
	sparse[i][j] = -1; //노드 i의 2^(j-1)번째 조상이 없다면 2^j번째 조상도 없음
	continue;
	}
	sparse[i][j] = sparse[sparse[i][j-1]][j-1]; //노드 i의 2^j번째 조상 확정
	}
	}
	}
	private static void setOrder(int cur) {
	in[cur] = ++count; //진입
	for(int next : input[cur]) {
	if(sparse[next][0] == 0) { //2^0번째 조상이 확정되지 않은 경우
	sparse[next][0] = cur; //2^0번째 조상을 확정
	setOrder(next); //DFS 탐색
	}
	}
	out[cur] = count; //진출
	}
	}

view raw LCA2_DFS.java hosted with ❤ by GitHub