[Do It! 코딩테스트 자바편(김종관)] 문제 074(백준 11437번)

느낀점

• 기본적인 LCA 문제다.
• 실제 LCA 구하는 함수는 간단히 구현 가능하지만, BFS로 각 노드의 depth를 설정하는 게 까다로웠다.
• 즉 BFS로 탐색하다가 이번 높이에 해당하는 모든 노드를 방문했을 때 depth를 1 증가해야 하는데, 나는 이를 못 떠올려서 교재를 코드 풀이를 보고 알았다.

문제

LCA(백준: 11437번)

내 풀이

import java.io.*;
import java.util.*;

public class Main {
    static int nodeCnt, queryCnt;
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
    static boolean[] visited;
    static int[] parent, depth;

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

        // 인접리스트 초기화
        for (int i = 0; i <= nodeCnt; i++) {
            tree.add(new ArrayList<>());
        }
        for (int i = 0; i < nodeCnt - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            tree.get(n1).add(n2);
            tree.get(n2).add(n1);
        }
        // 방문배열 초기화
        visited = new boolean[nodeCnt + 1];
        // 부모, 깊이 배열 초기화
        parent = new int[nodeCnt + 1];
        depth = new int[nodeCnt + 1];
        bfs(1);

        queryCnt = Integer.parseInt(br.readLine());
        for (int i = 0; i < queryCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());

            System.out.println(lca(n1, n2));
        }
    }

    private static int lca(int n1, int n2) {
        if (depth[n1] < depth[n2]) {
            int tmp = n1;
            n1 = n2;
            n2 = tmp;
        }

        while (depth[n1] != depth[n2]) {
            n1 = parent[n1];
        }

        while (n1 != n2) {
            n1 = parent[n1];
            n2 = parent[n2];
        }

        return n1;
    }

    private static void bfs(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visited[node] = true;

        int level = 1;
        int nowDepthNodeCnt = 1;
        int cnt = 0;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int next : tree.get(now)) {
                if (!visited[next]) {
                    queue.add(next);
                    visited[next] = true;

                    parent[next] = now;
                    depth[next] = level;
                }
            }

            cnt++;
            if (cnt == nowDepthNodeCnt) {
                cnt = 0;
                nowDepthNodeCnt = queue.size();
                level++;
            }
        }
    }
}