[BaekJoon] 11437 LCA (Java)

1.  문제 링크

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

2.  문제

요약

• N개의 정점으로 이루어진 트리가 주어지고 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번입니다.
• 두 노드의 쌍 M개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 50,000보다 작거나 같은 노드의 개수 N이 주어지고 두 번째 줄부터 N - 1개의 줄에 트리 상에서 연결된 두 정점이 주어집니다. 그 다음 줄에 1보다 크거나 같고 10,000보다 작거나 같은 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고 그 다음 줄부터 M개의 줄에는 정점의 쌍이 주어집니다.
• 출력: M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N, M;
    static HashMap<Integer, LinkedList<Integer>> tree;
    static int[][] nodes;
    static int[] parents, depth;

    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        tree = new HashMap<>();
        for (int node = 1; node <= N; node++) tree.put(node, new LinkedList<>());
        for (int edge = 0; edge < N - 1; edge++) {
            int node1 = scanner.nextInt(), node2 = scanner.nextInt();
            if (node1 == 1) {
                tree.get(node1).add(node2);
            } else if (node2 == 1) {
                tree.get(node2).add(node1);
            } else {
                tree.get(node1).add(node2);
                tree.get(node2).add(node1);
            }
        }
        M = scanner.nextInt();
        nodes = new int[M][2];
        for (int idx = 0; idx < M; idx++) {
            nodes[idx][0] = scanner.nextInt();
            nodes[idx][1] = scanner.nextInt();
        }
    }

    static void solution() {
        parents = new int[N + 1];
        for (int node = 1; node <= N; node++) parents[node] = node;
        depth = new int[N + 1];
        makeTree(1, -1);
        for (int idx = 0; idx < M; idx++)
            sb.append(findLCA(nodes[idx][0], nodes[idx][1])).append('\n');
        System.out.println(sb);
    }

    static void makeTree(int node, int prev) {
        if (prev != -1) {
            parents[node] = prev;
            depth[node] = depth[prev] + 1;
        }
        if (tree.get(node).size() == 1 && tree.get(node).get(0) == prev) {
            tree.get(node).remove(0);
            return;
        }
        for (int idx = 0; idx < tree.get(node).size(); idx++) {
            if (prev == tree.get(node).get(idx)) {
                tree.get(node).remove(idx);
                idx--;
                continue;
            }
            makeTree(tree.get(node).get(idx), node);
        }
    }

    static int findLCA(int node1, int node2) {
        int deeperNode = depth[node1] > depth[node2] ? node1 : node2;
        int shallowerNode = depth[node1] > depth[node2] ? node2 : node1;
        int deepDepth = depth[deeperNode], shallowDepth = depth[shallowerNode];
        if (deepDepth != shallowDepth) {
            while (deepDepth != shallowDepth) {
                deepDepth--;
                deeperNode = parents[deeperNode];
            }
        }
        while (deeperNode != shallowerNode) {
            deeperNode = parents[deeperNode];
            shallowerNode = parents[shallowerNode];
        }
        return deeperNode;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 해당 문제는 LCA 알고리즘을 이용하여 해결합니다.

LCA 알고리즘

• LCA(Lowest Common Ancestor), 즉 최소 공통 조상 알고리즘은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 구하는 알고리즘입니다.

동작 과정

1. 최소 공통 조상을 찾으려는 두 정점의 깊이를 구합니다.
2. 만약 두 정점의 깊이가 다르다면 깊이가 더 깊은 노드를 깊이가 더 낮은 노드의 깊이까지 노드를 올려줍니다.
3. 두 정점의 깊이를 맞췄다면, 두 정점의 조상이 같아질 때까지 같이 노드를 타고 올라갑니다.

• 주어진 트리 상에서 연결된 두 정점을 이용하여 HashMap을 이용해 연결 관계를 설정합니다.
• makeTree 메서드를 이용해 각 정점의 부모와 깊이를 구합니다.
  • 현재 방문한 정점인 node와 바로 직전에 방문한 정점인 prev를 매개변수로 받습니다.
  • 만약 prev가 -1이 아니라면, 즉 node가 루트가 아니라면 해당 정점의 부모는 prev로, 해당 정점의 깊이는 (prev의 깊이 + 1)로 설정합니다.
  • prev를 제외한 node에 연결되어있는 정점들에 대해서 node를 prev로, 연결되어있는 정점을 node로 하여 재귀를 통해 모든 정점의 부모와 깊이를 구합니다.
• findLCA 메서드를 통해 LCA 알고리즘을 수행합니다.
  • 두 정점 중 더 깊이가 깊은 정점을 deeperNode에, 더 깊이가 얕은 정점을 shallowerNode에 넣은 후에 두 정점의 깊이를 확인합니다.
  • 만약 두 정점의 깊이가 다르다면 deeperNode를 shallowerNode의 깊이와 같아질 때까지 deeperNode의 부모로 변경합니다.
  • 두 정점의 깊이가 같아졌다면, 두 정점이 같아질 때까지 자신의 부모로 두 정점을 변경해나갑니다.