[알고리즘] 백준 > #11437. LCA

문제링크

백준 #11437. LCA

풀이방법

문제 이름이나 내용에서 바로 알 수 있듯 LCA로 푸는 문제입니다! 최소공통조상이란, 두 정점 u,v가 있을 때 u이거나 u의 조상이면서 동시에 v이거나 v의 조상인 노드들 중 가장 깊은 노드를 뜻합니다~

문제 풀이는 두 단계로 구성되어 있습니다!
#1. 두 정점의 깊이가 같아질 때까지 더 깊은 정점에서 계속 부모로 이동
#2. 두 정점이 만날때까지 두 정점의 부모로 이동
쉽죠??

** 처음에 저는 두 정점이 입력되었을 때 번호가 낮은 노드가 부모가 되는줄알았어요; 그런 조건이 어디에도 쓰여있지 않죠?? 그래서 일단 edges라는 LikedList에 모두 넣어두고 root인 1번 노드부터 dfs로 트리를 구성했습니다!

코드

import java.util.LinkedList;
import java.util.Scanner;

public class LCA {
    static Node[] tree;
    static LinkedList<Integer>[] edges;
    static boolean[] isBuilt;
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        edges = new LinkedList[n + 1];
        for (int i = 1; i <= n; i++) edges[i] = new LinkedList<>();
        for (int i = 1; i < n; i++) {
            int nodeA = sc.nextInt();
            int nodeB = sc.nextInt();
            edges[nodeA].add(nodeB);
            edges[nodeB].add(nodeA);
        }

        tree = new Node[n + 1];
        tree[1] = new Node(0, 1);
        isBuilt = new boolean[n + 1];
        isBuilt[0] = true;
        isBuilt[1] = true;
        makeTree(1);

        int m = sc.nextInt();
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int nodeA = sc.nextInt();
            int nodeB = sc.nextInt();

            result.append(findLCA(nodeA, nodeB) + "\n");
        }
        System.out.print(result.toString());
    }

    static private void makeTree(int parent) {
        for (int child: edges[parent]) {
            if (!isBuilt[child]) {
                tree[child] = new Node(parent, tree[parent].depth + 1);
                isBuilt[child] = true;
                makeTree(child);
            }
        }
    }

    static private int findLCA(int nodeA, int nodeB) {
        if (tree[nodeA].depth > tree[nodeB].depth) return findLCA(tree[nodeA].parentId, nodeB);
        else if (tree[nodeA].depth < tree[nodeB].depth) return findLCA(nodeA, tree[nodeB].parentId);

        // 같은 depth에 있으면 두 노드가 같은 노드인지 확인
        if (nodeA == nodeB) return nodeA;
        else return findLCA(tree[nodeA].parentId, tree[nodeB].parentId);
    }
}

class Node {
    public int parentId;
    public int depth;

    public Node(int parentId, int depth) {
        this.parentId = parentId;
        this.depth = depth;
    }
}

🙇🏻‍♀️

보니까 제한시간이 더 짧은 LCA2 문제가 있더라구요?? 이것두 다음에 풀어볼 예정입니다!