[PS] 백준3584: 가장 가까운 공통 조상 (Java)

문제

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

 

---

풀이

해시 + 그래프 탐색

접근법

“공통 조상” 이라는 키워드만 보고서는 유니온 파인드를 생각했습니다.

그러나 “가장 가까운 공통 조상(Nearest Common Ancestor)”을 구하는 문제로써 Union-Find로 구할 시 루트노드가 나오기에 다른 방식으로 접근했습니다.

 

두 정점의 부모 노드만 탐색하면 되었기에 일반적인 그래프 탐색을 통해서 접근했습니다. (시간복잡도↓)

트리 자료구조로는 인접리스트를 활용했고, 자식 노드가 아닌 부모 노드를 탐색해야 했기에 부모를 기준으로 자식노드를 담는게 아닌 자식 노드를 기준으로 부모 노드를 담았습니다.

list.get(부모).add(자식) → list.get(자식).add(부모)

a와 b 노드의 공통되는 부모노드를 탐색하기위해 두 노드 중 하나의 노드를 기준으로 부모노드에 대한 정보를 HashSet을 통해서 기록했습니다.

신경써야할 부분으로는 a노드가 b노드의 부모가 되는 경우입니다. (예제 2번째 TestCase)

또한 나머지 노드의 부모를 탐색하는 과정에서는 Set에 있는 노드들과 Hit되는 경우가 있는지 확인하는 추가 로직을 작성했습니다.

Hit가 된다면 그 노드가 “가장 가까운 공통 조상”노드가 됩니다.

Miss일 경우 계속해서 부모노드를 탐색합니다.

 

마지막 검증으로는 두 노드의 공통 조상이 없는 경우였는데, 트리 구조 상 루트노드가 존재하기에 이러한 경우는 없다고 생각하고 코드를 작성했습니다.

다음은 소스코드입니다. (아래에 개선된 소스코드가 있으므로 참고해주세요.)

---

소스코드(228ms)

import java.io.*;
import java.util.*;

//BOJ_3584
public class Main {
    static int T, N, res;
    static List<List<Integer>> list;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        /**
         * 접근법
         * 두 노드의 겹치는 부모노드 탐색
         * List로 트리 구성 + HashSet으로 공통 부모 탐색
         * 검증
         * 1. 두 노드의 공통 부모가 없을 경우 -> 트리 구조상 불가능
         * 2. 한 노드가 나머지 노드의 부모가 되는 경우 -> 자기자신을 포함하여 Set추가
         * **/

        T = Integer.parseInt(br.readLine());
        while(T-- > 0) {
            N = Integer.parseInt(br.readLine());

            list = new ArrayList<>();
            for(int i=0; i<=N; i++) list.add(new ArrayList<>());

            for(int i=0; i<N-1; i++) {
                st = new StringTokenizer(br.readLine());

                int parent = Integer.parseInt(st.nextToken());
                int child = Integer.parseInt(st.nextToken());
                list.get(child).add(parent);
            }

            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            Set<Integer> aParent = new HashSet<>();
            aParent.add(a);
            while(!list.get(a).isEmpty()) {
                a = list.get(a).get(0);
                aParent.add(a);
            }

            while(!list.get(b).isEmpty()) {
                b = list.get(b).get(0);
                if(aParent.contains(b)) {
                    res = b;
                    break;
                }
                aParent.add(b);
            }

            sb.append(res).append("\\n");
        }

        System.out.println(sb);

    }
}

 

---

정리

기본적인 그래프 탐색 문제로써 별 어려움없이 풀이할 수 있었습니다.

 

+

다른 사람들의 풀이를 참조해본 결과 최대 10,000개의 노드에 대해서 List + Set 풀이가 비효율적이라는 것을 알 수 있었습니다.

 

각 인접리스트의 연결되는 정점은 최대 1개입니다.

편향트리의 경우 Set에 추가되는 객체는 10,000개입니다.

 

두가지의 이유로 배열로 변경하여 228ms -> 172ms로 단축시킬 수 있었습니다.

다음은 변경된 소스코드입니다.

---

소스코드(172ms)

import java.io.*;
import java.util.*;

//BOJ_3584
public class Main {
    static int T, N;
    static int[] node;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        T = Integer.parseInt(br.readLine());
        while(T-- > 0) {
            N = Integer.parseInt(br.readLine());

            node = new int[N+1];
            boolean[] v = new boolean[N+1];

            for(int i=0; i<N-1; i++) {
                st = new StringTokenizer(br.readLine());

                int parent = Integer.parseInt(st.nextToken());
                int child = Integer.parseInt(st.nextToken());
                node[child] = parent;
            }

            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            v[a] = true;
            while(node[a] != 0) {
                a = node[a];
                v[a] = true;
            }

            while(!v[b]) {
                b = node[b];
            }

            sb.append(b).append("\n");
        }

        System.out.println(sb);

    }
}

 

---

채점결과