[백준] 자바 11437 LCA

문제

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

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

입력

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

출력

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

---

테스트 케이스

 

입력 1

15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15

출력 1

2
4
2
1
3
1

 

 

---

접근

LCA (Lowest Common Ancestor) 알고리즘 기초 문제 입니다.

LCA 알고리즘 순서

 

1. 트리를 생성하여, 부모, 깊이(DEPTH)를 초기화해줌.(재귀)

 

2. 노드 A와 노드 B의 최소 공통 조상을 알고 싶다면, A와 B의 DEPTH를 같게 맞춤

 

3.노드 A와 노드 B에서 한칸씩 조상으로 올라가면서 서로 만날 때 종료! => 그게 최소 공통 조상임

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static ArrayList<Integer> tree[];
	static int parents[];
	static int depths[];
	static public void dfs(int current, int depth, int parent) {
		depths[current] = depth;
		parents[current] = parent;
		for(int nextNode : tree[current]) {
			if(nextNode != parent) {
				dfs(nextNode, depth+1, current);
			}
		}
	}
	static public int LCA(int a, int b) {
		int aDepth = depths[a];
		int bDepth = depths[b];
		while(aDepth > bDepth) {
			aDepth--;
			a = parents[a];
		}
		while(bDepth > aDepth) {
			bDepth--;
			b = parents[b];
		}
		while(a != b) {
			a = parents[a];
			b = parents[b];
		}
		return a;
	}
	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    int N = Integer.parseInt(br.readLine());
	    parents = new int[N+1];
	    depths = new int[N+1];
	    tree = new ArrayList[N+1];
	    for(int i=1; i<=N; i++) {
	    	tree[i] = new ArrayList<>();
	    }
	    for(int i=0; i<N-1; i++) {
	    	StringTokenizer st = new StringTokenizer(br.readLine());
	    	int a = Integer.parseInt(st.nextToken());
	    	int b = Integer.parseInt(st.nextToken());
	    	tree[a].add(b);
	    	tree[b].add(a);
	    }
	    dfs(1,1,0);
	    
	    int M = Integer.parseInt(br.readLine());
	    for(int i=0; i<M; i++) {
	    	StringTokenizer st = new StringTokenizer(br.readLine());
	    	int a = Integer.parseInt(st.nextToken());
	    	int b = Integer.parseInt(st.nextToken());
	    	
	    	int result = LCA(a,b);
	    	
	    	bw.append(String.valueOf(result+"\n"));
	    }
	    bw.flush();
	    bw.close();
	    br.close();
	    }
	}

---

주의

LCA