[DFS] 백준 - 3584번: 가장 가까운 공통 조상 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

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

 

 

위 문제는 예시에서 보이는 것처럼 어떠한 두 수가 주어졌을 때 이들의 가장 가까운 공통 부모 노드를 찾는 것이다.

 

나는 그래서 그래프를 짤 때 다음과 같이 했다.

위 그림처럼 노드들이 참조할 때 부모 -> 자식이 아닌

자식 -> 부모로 참조하였고 단방향 참조로 하였다.

뭔가 그게 더 쉽고 빠르게 풀 수 있을 것 같았다.(뇌피셜)

 

코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer>[] map;
    static boolean[] visit;
    static int n;
    static ArrayList<Integer> parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
        ArrayList<Integer> nums = new ArrayList<>();

        for (int i = 0; i < t; i++) {
            n = sc.nextInt();

            map = new ArrayList[n];
            visit = new boolean[n];
            parent = new ArrayList<>();

            for (int j = 0; j < n; j++) {
                map[j] = new ArrayList<>();
            }

            int a = 0;
            int b = 0;

            for (int j = 0; j < n - 1; j++) {
                a = sc.nextInt() - 1;
                b = sc.nextInt() - 1;

                map[b].add(a);
            }

            a = sc.nextInt() - 1;
            b = sc.nextInt() - 1;

            ArrayList<Integer> aParent = dfs(a);
            parent = new ArrayList<>();
            visit = new boolean[n];
            ArrayList<Integer> bParent = dfs(b);
            parent = new ArrayList<>();
            visit = new boolean[n];

            boolean check = false;

            for (int j = aParent.size() - 1; j >= 0; j--) {
                for (int k = bParent.size() - 1; k >= 0; k--) {
                    if (aParent.get(j).equals(bParent.get(k))) {
                        nums.add(aParent.get(j) + 1);
                        check = true;
                        break;
                    }
                }
                if (check)
                    break;
            }
        }

        for (Integer num : nums) {
            System.out.println(num);
        }
    }

    private static ArrayList<Integer> dfs(int start) {
        visit[start] = true;


        for (int i = 0; i < map[start].size(); i++) {
            if (!visit[map[start].get(i)] && map[start].size() != 0) {
                dfs(map[start].get(i));
            }
        }

        parent.add(start);

        return parent;
    }
}

 

코드가 조금 지저분한 것 같지만 읽어보면 쉬울 것이다.

 

테스트 케이스 수 t를 입력받아 t번 for문을 돌리고

 

노드 개수 n을 입력 받아 n -1까지 간선을 받는다.(n번째 입력은 두 노드를 받기 때문에 n-1까지)

그리고 받은 노드의 간선을 map에 넣어주는데 

이때 위에 말했던 것처럼 자식이 부모를 참조하도록 하였다.

그래서 map[b].add(a)를 해주었다.

 

그리고 dfs를 선택한 노드별로 돌려주고 중첩 for문은 가장 가까운 부모 노드를 찾기 위해서 하는데

리스트에 차는 순서가 제일 높은 부모부터 차기 때문에 인덱스는 큰 숫자에서 작은 숫자로 해주기 위해 저렇게 하였다.

돌다가 공통 부모 만나면 리스트에 넣어준다.

(테스트 케이스만큼 돌리기 때문에 리스트에 넣어줬다가 한 번에 출력할 것임)

 

이렇게 돌리고 나면 마지막에 가장 가까운 공통 조상을 print 해주면 된다.