[백준] 11437번 - LCA (java)

Baekjoon 11437 - LCA (클릭 시 이동)

문제

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
3 초	256 MB	12641	5564	3271	43.006%

입력

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

출력

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

풀이

제한시간이 3초면 java기준 3*2 +1인 7초내에 해결하면 되므로 O(NM)의 시간복잡도로도 해결할 수 있다.

하지만 LCA 알고리즘을 공부 해 보고자 LCA알고리즘으로 풀어보았다.

입력은 순서가 없는 그래프로 주어지며 루트노드는 무조건 1이므로 그래프를 탐색하는 과정이 필요하다.

LCA 알고리즘

1. DFS를 수행하며 각 노드의 DEPTH와 그 노드의 부모를 저장한다. (완전탐색)
2. 찾고자 하는 두 노드의 Depth가 같을 때 까지 부모를 찾는다.
3. 같은 Depth에서의 정점이 같지 않다면 둘 모두의 부모를 비교하고 같을 때 까지 수행한다.
4. 무조건 root에서 정점이 같기 때문에 3번의 과정을 계속 반복한다면 정답을 찾을 수 있다.

과정

DFS

static void dfs(int v, int d) {
    visited[v] = true;
    depth[v] = d;

    for (Node temp = graph[v]; temp != null; temp = temp.link) {
        if (!visited[temp.vertex]) {
            parent[temp.vertex] = v;    // 부모 정점을 저장.
            dfs(temp.vertex, d + 1);    // DFS 마저 탐색
        }
    }
}

LCA

static int lca(int a, int b) {
    while (depth[a] != depth[b]) {    // depth가 같지 않다면
        if (depth[a] > depth[b])    // 더 큰 depth의 부모를 찾아 올라간다.
            a = parent[a];
        else 
            b = parent[b];
    }

    while (a != b) {        // depth가 같다면 공통 조상을 찾을 때 까지 부모를 찾아 올라간다.
        a = parent[a];
        b = parent[b];
    }
    return a;
}

최종 소스코드

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

public class BJ_G3_11437_LCA {

    static int N, M;
    static int[] parent;
    static int[] depth;
    static boolean[] visited;
    static Node[] graph;
    static StringTokenizer st;

    static class Node {
        int vertex;
        Node link;

        public Node(int vertex, Node link) {
            super();
            this.vertex = vertex;
            this.link = link;
        }
    }

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

        N = Integer.parseInt(br.readLine());
        parent = new int[N + 1];
        depth = new int[N + 1];
        visited = new boolean[N + 1];
        graph = new Node[N + 1];

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph[start] = new Node(end, graph[start]);
            graph[end] = new Node(start, graph[end]);
        }
        dfs(1, 0);

        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            sb.append(lca(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            sb.append("\n");
        }
        System.out.println(sb.toString());

    }

    static void dfs(int v, int d) {
        visited[v] = true;
        depth[v] = d;

        for (Node temp = graph[v]; temp != null; temp = temp.link) {
            if (!visited[temp.vertex]) {
                parent[temp.vertex] = v;
                dfs(temp.vertex, d + 1);
            }
        }
    }

    static int lca(int a, int b) {
        while (depth[a] != depth[b]) {
            if (depth[a] > depth[b])
                a = parent[a];
            else 
                b = parent[b];
        }

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