백준 11437번 LCA (JAVA)

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

11437번: LCA

 

해당 문제는 LCA알고리즘을 이용하여 문제를 해결하였습니다.

LCA알고리즘을 사용하려면 먼저 노드들을 depth와 parent로 표시해야합니다.

 

LCA 로직은 다음과 같습니다.

1. 깊이가 더 깊은 노드를 더 낮은 노드까지 올려줍니다. 

2. 두 정점의 깊이가 같아졌으면 각각의 노드가 같은지 확인하고 같다면 해당 노드를 출력하고 다르면 조상을 올려다보며 조상이 같아질 때까지 노드를 타고 올라간다.

 

여기서 두 정점의 깊이가 같아졌을 때 둘이 같은지를 확인하는 이유는 1번으로인해 두 정점의 깊이가 같아졌을때 둘의 정점이 같아져 현재 정점이 최소 공통 조상이 되는 경우가 존재하기 때문입니다.

 

package BOJ.LCA;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_11437 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        List<Integer>[] map = new ArrayList[n+1];
        int[] parent = new int[n+1];
        int[] depth = new int[n+1];
        for(int i = 0 ; i <= n ; i++){
            map[i] = new ArrayList<>();
        }
        for(int i = 0 ; i < n-1 ; i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = stoi.apply(st.nextToken());
            int b = stoi.apply(st.nextToken());
            map[a].add(b);
            map[b].add(a);
        }
        Arrays.fill(parent,-1);
        parent[1] = 0;
        findParent(map,parent,depth,1,n);
//        System.out.println(Arrays.toString(parent));
        int m = stoi.apply(br.readLine());
        for(int i = 0 ; i < m ; i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = stoi.apply(st.nextToken());
            int b = stoi.apply(st.nextToken());
            System.out.println(lca(parent,depth,a,b));
        }
    }

    private static void findParent(List<Integer>[] map, int[] parent, int[] depth,int now,int n) {
        for(int i = 0 ; i < map[now].size() ; i++){
            int next = map[now].get(i);
            if(parent[next] == -1){
                depth[next] = depth[now] + 1;
                parent[next] = now;
                findParent(map,parent,depth,next,n);
            }
        }
    }
//    private static int lca(int[] parent,int[] depth,int a, int b) {
//        while(true){
//            if(a == b){
//                return a;
//            }else if(depth[a] < depth[b]){
//                b = parent[b];
//            }else if(depth[a] > depth[b]){
//                a = parent[a];
//            }else {
//                if(parent[a] == parent[b]){
//                    return parent[a];
//                }else{
//                    a = parent[a];
//                    b = parent[b];
//                }
//            }
//        }
//    }
    private static int lca(int[] parent,int[] depth,int a, int b) {
        if(a == b){
            return a;
        }else if(depth[a] < depth[b]){
            return lca(parent,depth,a,parent[b]);
        }else if(depth[a] > depth[b]){
            return lca(parent,depth,parent[a],b);
        }else {
            if(parent[a] == parent[b]){
                return parent[a];
            }else{
                return lca(parent,depth,parent[a],parent[b]);
            }
        }
    }
}