[BOJ_3584] 가장 가까운 공통 조상

설명

---

진작 맞추고 ==을 써서 틀렸었던 문제다. Integer와 같이 Wrapper class의 비교가 필요할때는 equals로 비교를 하는 것이 안전 한 것 같다. ==을 쓰면 아래 코드의 이 중 포문에서 node.get(i) == node2.get(j) 를 쓰면 25%에서 무조건 틀렸습니다가 뜬다. 그래서, 다른 사람 풀이를 참고했는데 사실상 다를 것이 없어서 일일이 넣어보면서 찾아냈는데 equals를 사용하니 맞았다.

 

우선, 코드 자체는 dfs로 아래 두 정점에 대해서 각 부모를 탐색해서 올라가는 식으로 구현하였다. 이런식으로 구현하면 처음 만나는 부모 노드가 가장 깊이가 깊은 노드이므로 별도의 신경을 쓰지 않고 구현 할 수 있다.

 

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int[] visited;
    static List<Integer>[] listNode;
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        int T = Integer.parseInt(tk.nextToken());
        List<Integer> node,node2;
        while (T-- > 0){
            tk = new StringTokenizer(in.readLine()," ");
            int N = Integer.parseInt(tk.nextToken());
            visited = new int[N + 1];
            node = new ArrayList<>();
            node2 = new ArrayList<>();
            listNode = new ArrayList[N + 1];
            for (int i = 0; i < listNode.length; i++){
                listNode[i] = new ArrayList<>();
            }
            for (int i = 1; i < N; i++){
                tk = new StringTokenizer(in.readLine()," ");
                int a = Integer.parseInt(tk.nextToken());
                int b = Integer.parseInt(tk.nextToken());
                listNode[b].add(a);
            }
            tk = new StringTokenizer(in.readLine()," ");
            int a = Integer.parseInt(tk.nextToken());
            int b = Integer.parseInt(tk.nextToken());
            node.add(a);
            dfs(a,node);
            visited = new int[N + 1];
            node2.add(b);
            dfs(b,node2);

            loop : for (int i = 0; i < node.size(); i++){
                for (int j = 0; j < node2.size(); j++){
                    if (node.get(i).equals(node2.get(j))) {
                        System.out.println(node.get(i));
                        break loop;
                    }
                }
            }
        }
    }

    private static void dfs(int idx, List<Integer> node){
        visited[idx] = 1;
        for (int parent : listNode[idx]){
            if(visited[parent] == 0){
                visited[parent] = 1;
                node.add(parent);
                dfs(parent,node);
            }
        }
    }
}

3584번: 가장 가까운 공통 조상