[BOJ] 백준 11437번 LCA (Java)

#11437 LCA

난이도 : 골드 3

유형 : 트리 / LCA

 

11437번: LCA

▸ 문제

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

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

▸ 입력

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

▸ 출력

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

 

 

문제 풀이  

LCA(Lowest Common Ancestor)는 주어진 두 노드 a,b의 최소 공통 조상을 찾는 알고리즘이다.

 

구상

1. 1번 루트노드를 기준으로 DFS탐색을 하면서 각 노드의 트리의 높이(h)와 부모 노드(parent)를 저장해준다.
2. LCA(a,b)가 주어진다.
   1. 해당 두 노드의 h를 일정하게 맞춘다 (a의 높이 == b의 높이)
   2. 각 부모노드가 일치할 때 까지 비교하여 구한다. (최대 LCA는 루트노드 1)

 

시뮬레이션

예제에 주어진 트리의 6번 노드와 15번 노드의 LCA를 구해보자.

1. 6번 노드의 높이는 3, 15번 노드의 높이는 5이므로, 15번 노드의 높이를 6번에 맞춰준다.

15번 높이 5, 6번 높이 3

 

2. 15번의 부모노드를 거슬러 올라가 높이가 3인 5번 노드로 맞춰줬다. 이젠 같은 부모가 나올 때 까지 값을 비교해준다.

5,6번노드 높이 일치

 

3.  5,6번 노드는 2번노드에서 가장 빠르게 만나는 것을 볼 수 있다. 

LCA는 2번노드

 

→ 따라서 6번, 15번노드의 LCA는 2번노드이다.

 

풀이 코드 

parent를 저장해줄 때는 DFS탐색을 사용해줬다. 그런데 LCA를 찾는 과정을 보면 탐색을 할 때 편향트리를 만나게되면 엄청나게 많은 반복을 돌려줘야할 수도 있고, 중복 연산을 할 수도 있다. 그러면 O(NM)이라는 시간복잡도를 갖게 되어 범위가 더 크게 주어질 경우 해당 알고리즘은 느려질 것이다.

 

그래서 범위가 더 큰 데이터를 다뤄야 할 경우, dp나 세그먼트 트리와 같은 더 효율적인 방식을 사용하여 구해야한다. LCA2 풀러가기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static List<Integer>[] list;
	static int[] parent, depth;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		parent = new int[n+1];
		depth = new int[n+1];
		list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		StringTokenizer st = null;
		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());
			
			list[a].add(b);
			list[b].add(a);
		}
		
		init(1,1,0);

		StringBuilder sb = new StringBuilder();
		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());
			sb.append(LCA(a,b)+"\n");
		}
		System.out.println(sb.toString());
	}
	
	static void init(int cur, int h, int pa) {
		depth[cur] = h;
		parent[cur] = pa;
		for(int nxt : list[cur]) {
			if(nxt != pa) {
				init(nxt, h+1, cur);
			}
		}
	}
	
	static int LCA(int a, int b) {
		int ah = depth[a];
		int bh = depth[b];
		
		while(ah > bh) {
			a = parent[a];
			ah--;
		}
		
		while(bh > ah) {
			b = parent[b];
			bh--;
		}
		
		while(a!=b) {
			a = parent[a];
			b = parent[b];
		}
		return a;
	}
}