백준 11438 Java

문제

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

알고리즘 설명

LCA는 두 점 사이의 최저공통 조상을 구하는 알고리즘이다.    
DFS를 통해서 그래프 노드들의 깊이와 부모를 구한 다음
1. 깊이를 맞추고
2. 같은 부모가 나올때까지 탐색
의 순서를 반복한다.

자기 자신의 부모만 저장하는 1차원 배열로 구현을 하면 
그래프의 깊이가 깊을 경우 무조건 TIME OUT이 발생하기 때문에
부모 배열을 2차원으로 미리 메모제이션 해놓는 것이 정석이다.
이때 값은 2^k 형태로 저장하는데 이해를 한 번 한 다음 외우는게 좋을 것 같다.

parent[j][i] = parent[parent[j][i-1]][i-1]

참조 사이트 : https://www.crocus.co.kr/660

구현 코드

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

public class Main {
	
	static ArrayList<Integer> [] list;
	
	static int [] depth;
	static int [][] parent;
	static boolean [] visited;
	
	static int N;
	static int K;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		list = new ArrayList [N+1];
		
		for (int i = 1; i<=N; i++) {
			list[i] = new ArrayList<Integer>();
		}
		
		for (int i = 1; i<N; i++) {
			StringTokenizer 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);
		}
		
		int temp = 1;
	    K = 0;
		while (temp <=N ) {
			temp<<=1;
			K++;			
		}
		
		
		depth  = new int [N+1];
		visited = new boolean [N+1];
		parent = new int [N+1][K];
		
		dfs(1,1);
				
		fillparent();  
		  
		int Q = Integer.parseInt(br.readLine());
		
		for (int i = 1; i<=Q; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int answer = getLca(a,b);
			System.out.println(answer);
		}
		
		
	}

	private static int getLca(int a, int b) {
		// TODO Auto-generated method stub
		// a기준으로
		if (depth[a] < depth[b]) {
			int temp = b;
			b = a;
			a = temp;
		} 
		
		// 높이 맞추기
		for (int i = K-1; i>=0; i--) {
			int diff = depth[a] - depth[b];
			
			if ((diff&(1<<i)) !=0) {
				a = parent[a][i];
			}
		}
		
		// 같으면 return;		
		if (a==b) return a;
		
		for (int i = K-1; i>=0; i--) {	
			if (parent[a][i] != parent[b][i]) {
				a = parent[a][i];
				b = parent[b][i];
			}	
		}				
		return parent[a][0];
	}

	private static void fillparent() {
		// TODO Auto-generated method stub
		for (int i = 1; i<K; i++) {
			for (int j = 1; j<=N; j++) {
				parent[j][i] = parent[parent[j][i-1]][i-1];
			}
		}
		
	}

	private static void dfs(int node, int dep) {
		// TODO Auto-generated method stub	
		visited[node] = true;
		depth[node] = dep;
		
		for (int i = 0; i<list[node].size(); i++) {	
			if (!visited[list[node].get(i)]) {
				dfs(list[node].get(i), dep+1);
				parent[list[node].get(i)][0] = node;
			}
		}
	}

}