[BOJ] 백준 11437. LCA

문제

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

11437번: LCA

---

풀이

최소 공통 조상을 찾는 문제입니다. 위 문제는 sparse table이나 세그먼트 트리를 사용하지 않고, dfs로도 구현이 가능합니다.

 

우선 입력 값을 Arraylist<>[] 배열에 넣어 트리 상의 연결된 두 정점을 표현합니다. 그리고 parents[] 배열과 depth[] 배열을 통해 각 정점의 부모와 깊이를 저장합니다. (findDepthAndParents 메서드)

 

 그럼 parents 배열과 depth 배열을 통해 최소 공통 조상을 찾을 수 있습니다. 

 

 첫째로, depth 배열을 통해 두 노드의 깊이가 같은지를 먼저 확인합니다. 만약 같지 않다면, 깊이가 깊은 정점의 부모를 찾으며 정점의 깊이를 맞춰줍니다.

 두 번째로, 동일한 깊이를 맞추었다면 두 정점이 같은지를 확인합니다. 만약 다르다면 같은 깊이의 다른 정점임으로, 두 정점의 부모를 동시에 하나씩 찾아가며 같은지를 확인합니다.

 

 위 과정을 통해 가장 가까운 공통 조상을 얻을 수 있습니다. 아래는 소스 코드입니다.

 

---

소스 코드

import java.util.ArrayList;
import java.util.Scanner;

public class B11437_LCA {
    static Scanner sc = new Scanner(System.in);
    static int N,M;
    static int[] parents,depths;
    static ArrayList<Integer>[] list;

    public static void main(String[] args) {
        input();
        findDepthAndParents(1,1);
        outputCase();
    }

    static void input(){
        N = sc.nextInt();
        list = new ArrayList[N+1];
        for(int i = 0;i<N+1;i++){
            list[i] = new ArrayList<>();
        }
        parents = new int[N+1];
        depths = new int[N+1];
        for(int i = 0;i<N-1;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            list[a].add(b);
            list[b].add(a);
        }
        M = sc.nextInt();
    }
    static void findDepthAndParents(int cur, int depth){
        depths[cur] = depth;
        for(int next:list[cur]){
            if(depths[next]==0) {
                parents[next] = cur;
                findDepthAndParents(next, depth+1);
            }
        }
    }

    static void outputCase(){
        for(int i =0;i<M;i++){
            int A = sc.nextInt();
            int B = sc.nextInt();
            System.out.println(findLCA(A,B));
        }
    }
    static int findLCA(int A, int B){
        while(depths[A]>depths[B]){
            A = parents[A];
        }
        while(depths[A]<depths[B]){
            B = parents[B];
        }
        while(A!=B){
            A = parents[A];
            B = parents[B];
        }
        return A;
    }
}