백준 문제 풀이 - 가장 가까운 공통 조상 3584번

📜 문제 이해하기

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.
두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.
예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.
루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

💡 문제 재정의

두 노드중에서 가장 가까운 공통 조상을 출력하라.

✏️ 계획 수립

먼저 Node Class를 만들어 Node instance를 생성할 수 있도록 한다.
그 후 node 입력을 받으면서 각 node들의 parent를 채워준다.
Node Class안에 get_ancestors 함수를 만드는데 이 함수는 자신의 공통 조상들을 전부 담아 보내주는 배열이다.
비교할 노드들의 조상들을 담은 배열을 얻었다면 bruteforce로 두개의 배열에 공통 조상이 있는지 탐색한다. 만약에 공통 조상이 존재한다면 가장 깊이가 깊은 곳에 있는지 확인 후 갱신한다.

💻 계획 수행

import sys


class Node:
    def __init__(self, _node):
        self.parent = None
        self.ancestor_list = []
        self.node = _node

    def get_ancestors(self):
        this_node = self
        self.ancestor_list.append(this_node)
        while this_node.parent:
            self.ancestor_list.append(this_node.parent)
            this_node = this_node.parent
        return self.ancestor_list

    def __eq__(self, other):
        return self.node == other.node


if __name__ == '__main__':
    T = int(sys.stdin.readline().strip())
    for _ in range(T):
        node_num = int(sys.stdin.readline().strip())
        node_list = [Node(i) for i in range(node_num + 1)]
        for _ in range(node_num - 1):
            parent, child = map(int, sys.stdin.readline().split())
            node_list[child].parent = node_list[parent]

        node1, node2 = map(int, sys.stdin.readline().split())
        node1_ancestor_list = node_list[node1].get_ancestors()
        node2_ancestor_list = node_list[node2].get_ancestors()

        min_ancestor_node = -1
        min_ancestor_depth = node_num
        for i, ancestor_node1 in enumerate(node1_ancestor_list):
            for j, ancestor_node2 in enumerate(node2_ancestor_list):
                if ancestor_node1 == ancestor_node2 and min_ancestor_depth > min(i, j):
                    min_ancestor_depth = min(i, j)
                    min_ancestor_node = ancestor_node1
        print(min_ancestor_node.node)

🤔 회고

트리의 부모 자식 트릭을 이용하여 문제를 해결하였다. 그래프의 BFS를 이용하여 문제를 해결할 수도 있을 것 같다.