백준 | 11437번. LCA 1 - 최소 공통 조상 문풀

⬛ 백준 11437번. LCA 1 - 최소 공통 조상 문풀

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

11437번: LCA

문제

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

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

입력

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

출력

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

---

💚 문제 접근 방식

LCA를 푸는 방법은 크게 2가지가 있다. 이 문제의 경우 질의 개수 10,000개, 노드 개수 50,000개 여서 비교적 데이터 크기가 큰 문제는 아니다. 따라서 일반적인 LCA 풀이 방식으로 구현할 수 있다.

1) 데이터 초기화하기

노드 N개에 대한 간선 N-1개의 정보를 양방향 간선으로 tree 에 담아준다.

visited, parent, depth 선언해준다.

DFS나 BFS로 트리의 루트부터 탐색하면서 각 노드의 (부모노드, 깊이) 정보 담아준다.

2) getLCA(a,b)로 두 노드의 LCA를 구해주기

→ (1) 더 깊이 큰 노드를 a 에 swap

→ (2) 깊이 큰 a노드의 깊이를 b와 같아질 때까지 parent 거슬러 올라감

→ (3) 깊이 같아진 상태에서는 a==b 될 때까지 동시에 한 칸씩 거슬러 올라가다가 같아지면 return a (=LCA)

💚 제출 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 11437번. 최소공통조상구하기 1 - LCA 문풀 
 * @author MYLG
 *
 */
public class Main {
	static ArrayList<ArrayList<Integer>> tree;
	static int[] parent;
	static int[] depth;
	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[nx] = cur;
					depth[nx] = depth[cur] + 1;
				}
			}
		}
	}
	//getLCA
	private static int getLCA(int a, int b) {
		//깊이 더 큰 애를 a에 담기 
		if(depth[a] < depth[b]) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		
		//깊이 같아질 때까지 맞추기
		while(depth[a] != depth[b]) {
			a = parent[a];//계속 올림(더 깊이 높은 애를)
		}
		//맞춰서 탈출했으면 이제 동시에 한 칸씩 올림
		while(a != b) {
			a = parent[a];
			b = parent[b];
		}
		return a;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int N = kb.nextInt();
		parent = new int[N+1];
		depth = new int[N+1];
		visited = new boolean[N+1];
		
		tree = new ArrayList<>();
		for(int i=0; i<=N; i++) {
			tree.add(new ArrayList<>());
		}
		
		for(int i=0; i<N-1; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			//양방향 간선 채우기
			tree.get(a).add(b);
			tree.get(b).add(a);
		}
		
		BFS(1);//정보 담기 
		
		//2) LCA 구하기
		int M = kb.nextInt();
		for(int i=0; i<M; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			System.out.println(getLCA(a, b));
		}
	}
}