[백준 - Java] 11437번 : LCA 최소 공통 조상

문제

www.acmicpc.net/problem/11437

11437번: LCA

 

LinkedList를 통해 각 정점들을 저장하고 연결해준다.

 

인접 리스트로 구현된 트리를 DFS로 탐색한다.

 

탐색하면서 각 노드의 깊이와 부모 노드를 배열에 저장한다.

왜냐? 각 노드의 부모 노드 값을 저장해두면, 두 개의 노드가 어디에 있든 따라 올라가다 보면 최소 공통 조상을 찾을 수 있기 때문!

깊이를 맞추는 이유는 그게 비교하기 편함! (같은 깊이에서 시작해야 만나는 순간을 찾기가 쉬움)

 

정점 1부터 깊이는 0, 부모 노드는 -1로 DFS를 시작한다.

 

탐색이 끝나면, 본격적으로 최소 공통 조상을 찾는다.

 

먼저 두 정점의 깊이를 똑같이 만들고, 같은 깊이부터 시작해 공통 조상을 찾는다.

두 정점의 깊이가 같아졌다면, 부모 배열을 타고 올라가며 값을 비교한다.

두 정점이 같은 값을 가지게 된다면 최소 공통 조상을 찾은 것!!

 

전체 코드

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	public static LinkedList<Integer>[] adjList;
	public static int[] parent;
	public static int[] depth;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// 인접리스트로 트리 표현 
		int N = sc.nextInt();
		adjList = new LinkedList[N+1];
		for (int i = 1; i <= N; i++) {
			adjList[i] = new LinkedList<Integer>();
		}

		for(int i = 0; i < N-1; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			adjList[a].add(b);
			adjList[b].add(a);
		}
		
		parent = new int[N+1];
		depth = new int[N+1];
		
		// DFS를 통해 깊이와 부모 노드 배열에 저장 
		dfs(1, 0, -1);

		int M = sc.nextInt();
		for(int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			// LCA 시작 
			int depthA = depth[a];
			int depthB = depth[b];
		
			while(depthA > depthB) {
				a = parent[a];
				depthA--;
			}
			
			while(depthB > depthA) {
				b = parent[b];
				depthB--;
			}
			
			while(a != b) {
				a = parent[a];
				b = parent[b];
			}
			
			System.out.println(a);
		}
	}

	public static void dfs(int cur, int d, int p) {
		depth[cur] = d;
		parent[cur] = p;
		
		for(int next : adjList[cur]) {
			if(next != p) {
				dfs(next, d+1, cur);
			}
		}
	}

}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2311437/src/Main.java

KwonMinha/BOJ