(백준) 가장 가까운 공통 조상 - 3584 [java]

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

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

 

🐢 설명

너무 어려운 트리문제를 맞닥뜨리고 충격을 먹고 골드 하위 문제 트리 문제를 풀려고 했다.

 

이 문제는 LCA 유형의 문제로 최단거리내 공통 조상을 찾는 문제이다.

 

문제접근은 먼저 인접리스트를 이용해서 부모 -> 자식의 단방향 그래프를 그리고, 추후 자식들이 부모를 찾아 올라가는 과정을 위해서 (자식 - 부모) 쌍의 map을 사용했다.

 

root에서 모든 자식들에 대한 트리 그래프가 완성되고 자식들이 자신의 부모를 알고나면 두개의 노드가 주어지는데 이들의 공통 부모를 찾아나서는 방식으로 접근했다.

 

1. root에서 각 노드들에 대한 높이를 구한다. 그 중 더 높이가 더 높은 (위치상 낮은) 노드를 찾아서 높이가 더 낮은 노드의 높이까지 맞춘다.

2. 높이를 맞춘 후에는 부모가 같아질 때까지 부모를 하나씩 같이 올린다.

 

다른풀이 (더 직관적이고 간단)

스터디를 같이하시는 분께서  푼 방법인데 훨씬 좋아보여서 적어본다.

 

트리를 부모 -> 자식관계로 구성하지 않고 역방향 (자식 -> 부모)관계로 그린다.

 

이 후 주어진 2개의 노드 각각에 대해서 Root 노드를 만날 때 까지 부모 노드를 탐색하면서 check한다. 두번째 탐색하는 노드에서 이미 check된 노드를 발견하면 해당 노드가 공통 노드이므로 바로 반환한다.

 

🐢코드 (내 풀이) (다른풀이는 적지 않는다)

package Gold이상문제_정리;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

public class 가장가까운공통조상_3584 {
    static int T, N;
    static StringBuilder answer = new StringBuilder();
    static ArrayList<Integer>[] adj;
    static HashMap<Integer, Integer> chPaMap = new HashMap<>();
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(br.readLine());

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

            chPaMap.clear();
            boolean[] isNotRoot = new boolean[N+1];

            adj = new ArrayList[N + 1];
            for (int i = 0; i <= N; i++)
                adj[i] = new ArrayList<>();

            String[] input;
            for (int i = 0; i < N - 1; i++) {
                input = br.readLine().split(" ");
                int parent = Integer.parseInt(input[0]);
                int child = Integer.parseInt(input[1]);

                isNotRoot[child] = true;
                adj[parent].add(child);
                chPaMap.put(child, parent);
            }

            input = br.readLine().split(" ");
            int nodeA = Integer.parseInt(input[0]);
            int nodeB = Integer.parseInt(input[1]);
            int root = 1;
            while (isNotRoot[root]) root++;
            findCommonParent(root, nodeA, nodeB);
        }
        System.out.print(answer);
    }

    private static void findCommonParent(int root, int nodeA, int nodeB) {
        int heightA = findNode(root, nodeA, 0);
        int heightB = findNode(root, nodeB, 0);

        if (heightA < heightB)
            matching(nodeA, nodeB, heightA, heightB);
        else
            matching(nodeB, nodeA, heightB, heightA);
    }

    private static void matching(int topNode, int botNode, int topH, int botH) {
        while (botH > topH) {
            botH--;
            botNode = chPaMap.get(botNode);
        }

        while (topNode != botNode) {
            topNode = chPaMap.get(topNode);
            botNode = chPaMap.get(botNode);
        }
        answer.append(topNode).append("\n");
    }

    private static int findNode(int root, int node, int height) {
        if (root == node) return height;

        int h = 0;

        for (int next : adj[root]) {
            h += findNode(next, node, height + 1);
        }

        return h;
    }
}

 

🐢 마무리

알고리즘은 항상 더 쉽게 풀 수 있는 방법이 있는것 같다. 조금 더 문제를 천천히 쉽게 바라보는 시야를 가지기위해 노력하자.