[JAVA]11437 LCA 공통 부모 노드 찾기(골드 3)

 📚 문제  

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

11437번: LCA

🔍 아이디어  

공통 조상을 찾는 문제입니다.

각 노드의 깊이를 먼저 BFS, DFS를 이용하여 계산합니다. (이때 부모 노드도 함께 지정해줍니다, parents 배열)

이후에 a,b 노드의 공통 조상을 찾는 경우 a의 깊이, b의 깊이를 비교하여 두 노드의 깊이가 동일할 때까지 부모로 이동하며 올라옵니다

두 노드의 깊이가 같아졌으면 두 노드를 함께 부모로 노드로 올리는것을 반복합니다. 해당 과정을 반복하다 동일 노드가 되면 해당 노드가 공통 부모 노드입니다.

 

참고로 해당문제는 더욱 최적화할 수 있어 플레티넘 5문제가 있습니다. 

 

여기서 주의해야 할 점은 부모 노드가 반드시 적은 숫자인 것이 아니라는 것입니다.

즉 아래와 같은 경우도 있을 수 있기 때문에 parents배열을 bfs/dfs 탐색하면서 채워주어야 정확한 값을 구해줄 수 있습니다.

 

📝 풀이 

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

public class Boj_11437_LCA {
    private static int[] depths;
    private static int[] parents;
    private static final List<List<Integer>> graph = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int nodeCnt = Integer.parseInt(br.readLine());
        //부모 노드를 적는다.
        parents = new int[nodeCnt];
        for (int i = 0; i < nodeCnt; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < nodeCnt - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;

            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        //각 정점의 깊이를 구한다.
        depths = new int[nodeCnt];
        bfs();

        //두 정점의 같은 노드 구한다.
        int tc = Integer.parseInt(br.readLine());
        for (int i = 0; i < tc; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            sb.append(lca(a, b)).append("\n");
        }
        System.out.println(sb);

    }

    private static int lca(int a, int b) {
        //일단 두 깊이가 같아 질때까지 끌어올린다.
        if (depths[a] > depths[b]) {
            //a를 끌어 올린다.
            while (depths[a] != depths[b]) {
                a = parents[a];
            }

        } else if (depths[a] < depths[b]) {
            //b를 끌어 올린다.
            while (depths[a] != depths[b]) {
                b = parents[b];
            }
        }

        //두 노드를 같이 올린다.
        while (a != b) {
            a = parents[a];
            b = parents[b];
        }

        return a + 1;
    }

    private static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        int level = 1;
        depths[0] = level;
        parents[0] = 0;

        while (!q.isEmpty()) {
            level++;
            int size = q.size();

            for (int i = 0; i < size; i++) {
                Integer parent = q.poll();
                for (Integer child : graph.get(parent)) {
                    if (depths[child] == 0) { //방문하지 않은 경우만 방문한다
                        depths[child] = level;
                        parents[child] = parent;
                        q.add(child);
                    }
                }
            }
        }
    }
}