[BOJ] 11437번 LCA

개요

트리의 최소 공통 조상을 찾는 문제

문제링크

코드

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

public class Baekjoon11437 {
    public static ArrayList<Integer>[] tree;
    public static boolean[] isVisited; 
    public static int[] parents;
    public static int[] depths;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        tree = new ArrayList[n+1];
        isVisited = new boolean[n+1];
        parents = new int[n+1];
        depths = new int[n+1];
        for (int i = 0; i < tree.length; i++) 
            tree[i] = new ArrayList<>();
        
        
        int from, to;
        for (int i = 0; i < n-1; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            tree[from].add(to);
            tree[to].add(from);
        }
        
        isVisited[1] = true;
        dfs(1, 0);

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            
            bw.write(LCA(from, to)+"\n");
        }
        bw.flush();
        
        
    }

    public static void dfs(int node, int depth) {
        int child;
        depths[node] = depth;
        for (int i = 0; i < tree[node].size(); i++) {
            child = tree[node].get(i);
            if(!isVisited[child]) {
                parents[child] = node;
                isVisited[child] = true;
                dfs(child, depth + 1);
            }
        }
    }

    public static int LCA(int node1, int node2) {
        while(true) {
            if(depths[node1] == depths[node2]) {
                if(node1 == node2)
                    return node1;
                else {
                    node1 = parents[node1];
                    node2 = parents[node2];
                }
            }
            else {
                if(depths[node1] > depths[node2]) 
                    node1 = parents[node1];
                else 
                    node2 = parents[node2];
            }
        }
    }
}

해결 과정

1. 트리를 탐색하면서 parents배열에 각 노드들의 부모노드를 저장하고 각 노드의 깊이를 depths배열에 저장한다.

2. 최소 공통 노드를 확인할 노드 2개를 입력받아 두 노드의 깊이가 같아지도록 한 쪽 노드를 parents배열을 이용해 부모노드로 이동하며 깊이를 맞춘다.

3. 깊이가 같아졌으면 노드의 값을 비교해 다르면 한 칸씩 부모노드로 이동해 다시 비교하고 노드의 값이 같으면 공통 조상 노드이므로 노드의 값을 반환한다.

위와 같은 방법으로도 구할 수 있지만 트리의 크기가 매우 커지면 이 방법은 시간이 오래걸린다. 두 노드의 깊이 차이가 N이라고 하면 O(N)만큼의 시간이 걸리는데 이 시간을 O(LogN)만큼 단축시킬 수 있다. 그 방법은 다음 포스팅에서 다루겠다.

결과