백준 11437 LCA java

문제 소개 www.acmicpc.net/problem/11437

내용

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

해결 방법

아이디어

1. dfs를 통해서 각 노드의 depths와 자기 자신의 parent를 각각 depths[]와 parents[][0] 저장한다.

2. parents[][] 배열을 통해서 각각 노드의 2의 배수의 조상을 저장한다.

3. 구하고자 하는 a, b의depth를 마춰춘다.

4. a와 b가 같은지 체크

5. 같지 않다면 parents[][] 배열을 통해서 가장 높은 2의 배수의 조상이 같은지 확인하며 다르면 a,b를 해당 조상으로 업데이트 후 반복한다.

6. 이후 그렇게 업데이트된 a혹은 b의 직속 부모인 parents[a][0], parents[b][0] 둘중 하나를 리턴한다. 

실제 풀이 코드

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

        int n = Integer.parseInt(br.readLine());

        List<List<Integer>> adjList = new ArrayList();
        for (int i = 0; i <= n; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            String[] split = br.readLine().split(" ");
            int from = Integer.parseInt(split[0]);
            int to = Integer.parseInt(split[1]);

            adjList.get(from).add(to);
            adjList.get(to).add(from);
        }

        boolean[] visited = new boolean[n + 1];
        int[] depths = new int[n + 1];
        int[][] parents = new int[n + 1][20];

        dfs(1, 0, depths, parents, adjList, visited);
        setParent(n, parents);

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

        for (int i = 0; i < m; i++) {
            String[] split = br.readLine().split(" ");
            int from = Integer.parseInt(split[0]);
            int to = Integer.parseInt(split[1]);

            sb.append(LCA(from, to, depths, parents)).append(System.lineSeparator());
        }
        System.out.println(sb.toString());
    }

    private static int LCA(int from, int to, int[] depths, int[][] parents) {
        if (depths[from] > depths[to]) {
            int temp = from;
            from = to;
            to = temp;
        }

        for (int n = 19; n >= 0; n--) {
            if (depths[to] - depths[from] >= (1 << n)) {
                to = parents[to][n];
            }
        }

        if (from == to) return from;

        for (int n = 19; n >= 0; n--) {
            if (parents[from][n] != parents[to][n]) {
                from = parents[from][n];
                to = parents[to][n];
            }
        }
        return parents[from][0];
    }

    private static void setParent(int n, int[][] parents) {
        for (int j = 1; j < 20; j++) {
            for (int i = 1; i <= n; i++) {
                parents[i][j] = parents[parents[i][j - 1]][j - 1];
            }
        }
    }

    private static void dfs(int current, int depth, int[] depths, int[][] parents, List<List<Integer>> adjList, boolean[] visited) {
        visited[current] = true;
        depths[current] = depth;

        for (int child : adjList.get(current)) {
            if (visited[child]) continue;

            parents[child][0] = current;
            dfs(child, depth + 1, depths, parents, adjList, visited);
        }
    }
}

결과

LCA2를 먼저 풀어봐서 DP를 활용한 LCA로 해결하였다. 

n이 50,000이며, m이 10,000이라서 dp를 적용하지 않고 하나씩 타고 올라가서 해결하는 방법이 O(nm)으로 아슬아슬하게 LCA에서는 통과하는가보다. 

 

그래도 더 빠른 알고리즘을 알고있는데 굳이 느린방법을 연습할 필요는 없다고 생각하여 O(mlogn)시간복잡도인 DP+LCA 방법으로 연습하였다.