문제 설명

문제 분석

질의 개수가 10,000개이며 노드 개수가 50,000개로 비교적 데이터가 크지 않아 일반적인 방식의 LCA 알고리즘으로 구현하면 되는 문제다.

슈도코드

구현

public class 최소공통조상구하기1 {
    static int[] depth;
    static int[] parent;
    static boolean[] visited;
    static List<Integer>[] tree;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine()); // 노드 수
        tree = new ArrayList[N + 1];
        depth = new int[N + 1];
        parent = new int[N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < N; i++) {
            tree[i] = new ArrayList<>();
        }
        // 트리 연결
        StringTokenizer tokenizer;
        for (int i = 0; i < N -1; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int s = Integer.parseInt(tokenizer.nextToken());
            int e = Integer.parseInt(tokenizer.nextToken());
            tree[s].add(e);
            tree[e].add(s);
        }

        BFS(1); // depth 구함

        int M = Integer.parseInt(reader.readLine());
        for (int i = 0; i < M; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int a = Integer.parseInt(tokenizer.nextToken());
            int b = Integer.parseInt(tokenizer.nextToken());
            int LCA = executeLCA(a, b);
            System.out.println(LCA);
        }
    }

    static int executeLCA(int a, int b) {
        if(depth[a] < depth[b]) {
            int temp = a;
            a = b;
            b = temp;
        }

        // 두 노드의 depth 맞추기
        while(depth[a] != depth[b]) {
            a = parent[a];
        }

        // 같은 조상이 나올 때까지 한 칸씩 올림
        while(a != b) {
            a = parent[a];
            b = parent[b];
        }

        return a;
    }

    static void BFS(int node) {
        Queue<Integer> q = new LinkedList<>();
        q.add(node);
        visited[node] = true;
        int level = 1;
        int currentSize = 1;
        int cnt = 0;

        while(!q.isEmpty()) {
            int currentNode = q.poll();
            for (int next : tree[currentNode]) {
                if(!visited[next]) {
                    visited[next] = true;
                    q.add(next);
                    parent[next] = currentNode; // 부모 노드 저장
                    depth[next] = level; // 노드 depth 저장
                }
            }

            cnt++;

            if(cnt == currentSize) {
                cnt = 0;
                currentSize = q.size();
                level++;
            }
        }

    }
}