[백준] 11437번 LCA

문제 설명

• https://www.acmicpc.net/problem/11437
• Gold 3
• 소요 시간 : 11분

문제 풀이

• 일반적인 LCA 문제이다.
• O(N) 알고리즘을 사용해도 괜찮아 보여서 사용했다.
• 풀이는 아래와 같다.

  1. 트리를 루트부터 DFS를 진행하여 각 노드의 깊이, 부모 노드를 저장해준다.
  2. 두개의 노드가 주어졌을 때 우선 두 노드의 높이가 같아질 때까지 한쪽을 계속 부모 노드로 이동 시킴.
  3. 같은 높이에서 부터 두 노드의 부모를 동시에 탐색하며 노드가 같아질 경우 LCA

소스 코드 (JAVA)

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

class Main {
    static int N, M;
    static int[] depth, parent;
    static List<List<Integer>> map = new ArrayList<>();

    // a, b의 공통 조상 리턴
    static int solve(int a, int b) {
        // a, b 높이 맞춰 주기
        while(depth[a] > depth[b]) {
            a = parent[a];
        }

        while(depth[a] < depth[b]) {
            b = parent[b];
        }

        // 공통 조상 찾기
        while(a != b) {
            a = parent[a];
            b = parent[b];
        }
        return a;
    }

    // depth, parent 초기화
    static void init(int cur, int dep, int before) {
        depth[cur] = dep;
        parent[cur] = before;
        for (int i = 0; i < map.get(cur).size(); i++) {
            int next = map.get(cur).get(i);
            if (next != before) init(next, dep+1, cur);
        }
    }

    static void input() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        //초기화
        for (int i = 0; i <= N; i++)
            map.add(new ArrayList<>());
        depth = new int[N+1];
        parent = new int[N+1];

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

        //트리 데이터 초기화
        init(1, 1, 0);

        //정답 출력
        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            //a, b의 공통 조상 출력
            bw.write(solve(a, b) + "\n");
        }
        bw.flush();
    }

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

/**
 * LCA (22:43)
 *
 * N : 정점 개수 (<= 50000)
 * M : 노드 쌍 개수 (<= 10000)
 * 루트는 1번 노드
 * 노드 쌍의 가장 가까운 공통 조상이 몇번인지 출력
 *
 * - O(N) LCA를 사용해도 될 듯 (제한시간 3초)
 *
 * N
 * a b
 * ..
 * M
 * a b
 * ..
 */