[BOJ][Java] 11437. LCA

문제

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

 

 

문제 풀이

DFS로 parent/depth 저장 → 깊이 맞추기 → 함께 올라가면서 같아지는 지점 반환

 

1. 트리 DFS로 각 노드의 부모, 깊이 저장하기

• 루트부터 자식으로 내려가면서 parent, depth 배열에 저장
• 루트(1)는 부모를 자기 자신(1)으로, 깊이는 0으로 (dfs(1, 1, 0))

 

2. LCA 구하기

• 깊이 맞추기
  • 더 깊은 쪽을 부모로 올려서 depth[a] == depth[b]로 만듦.
• 공통 조상 찾기
  • a == b가 될 때까지 둘 다 parent로 올라감.
  • 같아지면 그 노드가 LCA.

 

유의할 점 (예외)

a, b가 같은 노드이거나, 한쪽이 다른 쪽의 조상일 수 있다.
이때 LCA는 그 노드 자신이어야 한다.

 

잘못된 코드

while (parent[a] != parent[b]) {
    a = parent[a];
    b = parent[b];
}
return parent[a]; // 부모를 반환

공통 부모를 찾는 것이라서 a, b의 부모가 같을 때까지 올라가고 같으면 부모를 반환했다.
이럴 경우, 깊이를 맞춘 후에 두 노드가 같을 때 문제가 발생한다.
두 노드의 부모를 반환 → 한 단계 더 올라간 값을 반환해서 오답이 출력된다.

 

수정한 코드

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

return a;

 

코드

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

public class Main {
    static int n;
    static int[] parent;
    static int[] depth;
    static List<Integer>[] edge;

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

        n = Integer.parseInt(br.readLine()); // 노드 개수
        parent = new int[n + 1];
        depth = new int[n + 1];
        edge = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            edge[i] = new ArrayList<>();
        }

        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());

            edge[a].add(b);
            edge[b].add(a);
        } // 입력1 끝

        dfs(1, 1, 0); // 부모, 깊이 저장

        StringBuilder sb = new StringBuilder();
        int m = Integer.parseInt(br.readLine());

        while (m-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            sb.append(lca(a, b)).append("\n");
        } // 입력2 & 연산

        System.out.println(sb);
    }

    static void dfs(int cur, int p, int d) {
        parent[cur] = p;
        depth[cur] = d;

        for (int next : edge[cur]) {
            if (next == p)
                continue;

            dfs(next, cur, d + 1);
        }
    }

    static int lca(int a, int b) {
        // 깊이 맞추기
        while (depth[a] < depth[b])
            b = parent[b];

        while (depth[a] > depth[b])
            a = parent[a];

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

        return a;
    }
}