boj 11437 LCA

www.acmicpc.net/problem/11437

11437번: LCA

 

 

LCA 알고리즘으로 해결하였습니다.

 

정점이 N개이고, N - 1개의 간선정보가 입력주어 주어집니다.

u와 v를 서로 연결시켜주고 루트노드인 1부터 dfs를 돌려서 각 노드의 높이를 먼저 구해줍니다.

높이를 구하는 과정에서 자식노드가 next로 나오는데 next의 첫번째 조상노드를 v로 저장해둡니다.

 

dfs순회가 끝나면 이제 각 노드의 2^N번째 조상노드를 저장해줍니다.

첫번째 조상노드부터 차례대로 저장하여 순회하면 시간적으로 비효율적이고,

1, 2, 4, 8, ~ 2^N번째 조상노드만 저장해줘도 모든 조상노드를 탐색할 수 있습니다.

 

그리고 u, v 정점이 입력으로 들어오면 lca함수를 통해 최소 공통 조상노드를 구해줍니다.

먼저 노드의 depth가 높은쪽을 y에 맞춘 후에 y노드의 높이를 x와 같게 맞춰줍니다.

그 다음 x와 y의 조상이 같아질때까지 올라가주면 됩니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> list[] = new ArrayList[50001];
    static boolean visit[];
    static int parent[][] = new int[50001][17];
    static int depth[] = new int[50001];
    static int N, M;
 
    static void dfs(int v, int d) {
        visit[v] = true;
        depth[v] = d;
 
        for (int i = 0; i < list[v].size(); i++) {
            int next = list[v].get(i);
 
            if (visit[next])
                continue;
 
            parent[next][0] = v;
            dfs(next, d + 1);
        }
    }
 
    static void func() {
        dfs(1, 1);
        for (int j = 1; j < 17; j++) {
            for (int i = 1; i <= N; i++) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            }
        }
    }
 
    static int lca(int x, int y) {
        if (depth[x] > depth[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }
 
        for (int i = 16; i >= 0; i--) {
            if (depth[y] - depth[x] >= (1 << i)) {
                y = parent[y][i];
            }
        }
 
        if (y == x)
            return x;
 
        for (int i = 16; i >= 0; i--) {
            if (parent[x][i] != parent[y][i]) {
                x = parent[x][i];
                y = parent[y][i];
            }
        }
 
        return parent[x][0];
    }
 
    static void solve() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            sb.append(lca(u, v) + "\n");
        }
        
        System.out.print(sb.toString());
    }
 
    static void input() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        visit = new boolean[N + 1];
        for (int i = 1; i <= N; i++)
            list[i] = new ArrayList<>();
 
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            list[u].add(v);
            list[v].add(u);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        solve();
    }
}