백준 11437번: LCA (Java)

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

11437번: LCA

 

 

 

 

 

 

 

---

 

풀이

'뭔 LCA여' 할 수 있겠지만, 질문 게시판의 글에서 알 수 있듯이 naive한 구현으로도 풀릴 수 있도록 설계한 문제입니다. M번의 쿼리마다 최소 공통 조상을 찾는데 순회해야하는 횟수는 최대 O(N)이므로, O(MN)으로 가능합니다.

다만 저는 각 정점 별 parent만 기록한 후, 처음 정점에서 위로 쭉 올라가면서 방문한 정점을 Set에 넣어주고, 두 번째 정점에서 올라가다 Set에 있는 원소를 만나면 LCA를 구하는 방식으로 처리했는데, set의 단위 연산이 좀 무거워서 시간 초과가 발생했습니다.

따라서, 정점 별로 parent만 구하지 말고, depth도 구한 후 두 정점의 depth가 같아지는 시점까지 올라간 후 거기서부터 같아질 때까지 조상을 찾아나서면 됩니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] parents, depth;
    static List<List<Integer>> graph;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        parents = new int[N+1];
        depth = new int[N+1];
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < N-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        parents[1] = -1;
        dfs(1, 0);
        
        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            while (depth[u] > depth[v]) u = parents[u];
            while (depth[u] < depth[v]) v = parents[v];
            while (u != v) {
                u = parents[u];
                v = parents[v];
            }
            sb.append(u+"\n");
        }
        System.out.println(sb.toString());
    }
    
    static void dfs(int cur, int d) {
        depth[cur] = d;
        for (int nxt: graph.get(cur)) {
            if (parents[nxt] != 0) continue;
            parents[nxt] = cur;
            dfs(nxt, d+1);
        }
    }
}