[백준] 11437번*/ - LCA (골드3)

https://www.acmicpc.net/problem/11437
union-find 생각 => 틀림

입력 후 깊이와 부모 저장 => 더 깊은 곳의 부모를 가져와서 같아지면 출력

import java.io.*;
import java.util.*;
public class Main {
    static int n,m;
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
    static int[] d, p;
    static boolean[] vis;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        // n
        n = Integer.parseInt(br.readLine());
        d = new int[n+1];
        p = new int[n+1];
        vis = new boolean[n+1];
        // tree 생성
        for(int i=0;i<=n;i++){
            tree.add(new ArrayList<>());
        }
        // n-1개 노드 정보 
        for(int i=0;i<n-1;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree.get(a).add(b);
            tree.get(b).add(a);
        }
        // d, p 구하기
        dfs(1,0,0);
        // m
        m = Integer.parseInt(br.readLine());
        // 공통 조상 알아보기
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            System.out.println(lca(a,b));
        }
    }
    static void dfs(int cur, int depth, int parent){
        vis[cur] = true;
        d[cur] = depth;
        p[cur] = parent;

        for(int t : tree.get(cur)){
            if(!vis[t]){
                dfs(t,depth+1,cur);
            }
        }
    }
    static int lca(int a, int b){
        // a가 더 깊은 depth를 가지게 하기
        if(d[a]<d[b]){
            int tmp = a;
            a=b;
            b=tmp;
        }
        // depth 동일하게 만들기
        while(d[a]!=d[b]){
            a = p[a];
        }
        if(a==b) {return a;}

        // 동일한 부모 찾기
        while(p[a]!=p[b]){
            a=p[a];
            b=p[b];
        }

        return p[a];
    }
}

10/29

import java.util.*;
import java.io.*;
public class Main {
    static int n,m;
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
    static int[] p, d;
    static boolean[] vis;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        for(int i=0;i<=n;i++){
            tree.add(new ArrayList<>());
        }
        p = new int [n+1];
        d = new int [n+1];
        vis = new boolean[n+1];

        for(int i=0;i<n-1;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree.get(a).add(b);
            tree.get(b).add(a);
        }
        dfs(1,0,0);

        m = Integer.parseInt(br.readLine());
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            System.out.println(lca(a,b));
        }
    }
    static void dfs(int s, int depth, int parent){
        vis[s]= true;
        d[s] = depth;
        p[s] = parent;

        for(int c : tree.get(s)){
            if(!vis[c]){
                dfs(c, depth+1, s);
            }
        }

    }
    static int lca(int a, int b){
        if(d[a]<d[b]){
            int tmp = b;
            b=a;
            a=tmp;
        }
        while(d[a]!=d[b]){
            a = p[a];
        }

        if(a==b) return a;

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