[JAVA/LCA] 백준 11438 LCA 2

1. 문제

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

11438번: LCA 2

 

2. 풀이

LCA를 구현하는 문제다. LCA는 최소 공통 조상을 구하는 문제다. 

LCA를 구현하기 위해 현재 노드의 부모를 2차원 배열에 저장하는 방법과 1차원 배열에 저장하는 방법이 있다.

1) 부모를 2차원 배열에 저장

부모를 2차원 배열에 저장할 경우 첫번째 차원에는 노드의 인덱스가 담기고 두번째 차원에는 노드의 2^i번째 조상 노드가 저장된다. 

2) 부모를 1차원 배열에 저장

이렇게 하면 1차원 배열에는 현재 인덱스의 바로 위 부모가 담긴다. 이를 사용해 풀이 할 경우, while문을 사용해서 둘의 depth가 같을 때 까지 부모노드로 올려주면 된다.

 

+) 더 자세한 설명은.... 추후에.....

 

3. 코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

// LCA

public class Main_11438 {
    
    static List<List<Integer>> arr; // 인접리스트 그래프
    static int[] depth; // 노드의 depth 저장
    static int[][] parents; // depth별 부모노드 저장
    static int n;
    static int k;
    
    // 노드 depth와 노드의 부모 노드 저장
    private static void dfs(int node, int cnt) {
        depth[node] = cnt; // root의 depth는 1
        
        for(int next : arr.get(node)) {
            if(depth[next] == 0) {
                parents[next][0] = node;
                dfs(next, cnt + 1);
            }
        }
    }
    
    // 노드별 2^i 번째 조상노드 저장
    private static void fillParents() {
        for(int i = 1; i < k; i++) { 
            for(int j = 1; j <= n; j++) {
                parents[j][i] = parents[parents[j][i-1]][i-1];
            }
        }
    }
    
    private static int lca(int a, int b) {
        
        // depth가 낮은쪽을 기준으로 설정
        if(depth[a] < depth[b]) { 
            int tmp = a; 
            a = b; 
            b = tmp;
        }

        // depth가 큰 a의 depth를 b의 depth를 맞추고
        // 맞춘 depth의 조상노드로 대체
        for(int i = k - 1; i >= 0; i--) {
            if(Math.pow(2, i) <= depth[a] - depth[b]) 
                a = parents[a][i];
        }
        
        // depth 맞춘 후 조상노드가 b면 (= a의 조상노드가 b면) 종료
        if(a == b) 
            return a;
        else {
            // 두 노드는 같은 depth이므로
            // 같이 2승씩 올라가며 공통부모 바로 아래까지 올라감
            for(int i = k - 1; i >= 0; i--) {
                if(parents[a][i] != parents[b][i]) {
                    a = parents[a][i];
                    b = parents[b][i];
                }
            }
        }
        
        return parents[a][0];
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());

        // 최대 depth 구하기
        k = 0;
        int tmp = 1;
        while(tmp <= n) {
            tmp <<= 1;
            k++;
        }
        
        
        depth = new int[n+1]; // i 노드의 depth 저장, root는 1
        parents = new int[n+1][k]; // depth별 부모노드 저장
        
        arr = new ArrayList<List<Integer>>();
        for(int i = 0; i <= n; i++) 
            arr.add(new ArrayList<Integer>());
        
        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());
            arr.get(a).add(b);
            arr.get(b).add(a);
        }
        
        dfs(1, 1);
        fillParents();
        

        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());
            
            int lca = lca(a, b);
            bw.write(lca + "\n");
            
        }
        
        bw.flush();
        bw.close();
        br.close();

    }

}