[파이썬] 트리 알고리즘을 활용한 최소 공통 조상 (LCA) 찾기

04 Sep 2023

python

트리 알고리즘(Tree Algorithm)은 트리 구조에서 다양한 문제를 해결하는 데 사용되는 알고리즘입니다. 이 중에서도 최소 공통 조상(Lowest Common Ancestor, LCA)을 찾는 알고리즘은 많은 문제 해결에 활용되며, 특히 그래프와 관련된 문제에서 유용합니다.

최소 공통 조상 (LCA)란?

최소 공통 조상 (LCA)은 두 개의 노드가 주어졌을 때, 두 노드의 가장 가까운 공통 상위 조상을 찾는 문제입니다. 여기서 상위 조상은 노드의 부모, 조부모, 증조부모 등을 의미합니다. LCA 문제는 트리 구조에서 각 노드의 부모 노드를 찾을 수 있다는 가정하에 해결할 수 있습니다.

LCA 알고리즘 구현하기

다음은 Python으로 LCA 알고리즘을 구현한 예시 코드입니다.

# 트리 노드 클래스 정의
class Node:
    def __init__(self, key):
        self.key = key
        self.children = []

# LCA를 찾는 함수
def findLCA(root, node1, node2):
    if root is None:
        return None
    if root == node1 or root == node2:
        return root
    lca = None
    for child in root.children:
        child_lca = findLCA(child, node1, node2)
        if child_lca is not None:
            if lca is not None:
                return root
            else:
                lca = child_lca
    return lca

# 트리 생성
root = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)

root.children = [node2, node3, node4]
node2.children = [node5, node6]

# LCA 찾기
lca_node = findLCA(root, node5, node6)
print("LCA:", lca_node.key)

위 코드에서는 Node 클래스를 정의하고, 두 개의 노드를 입력으로 받아 최소 공통 조상을 찾는 findLCA 함수가 구현되어 있습니다. 트리를 생성한 후 findLCA 함수로 LCA를 찾을 수 있습니다.

위 예시에서는 트리 구조가 다음과 같이 구성되어 있습니다.

이 경우, 노드 5와 6의 최소 공통 조상은 노드 2입니다. 따라서 출력 결과는 LCA: 2가 됩니다.

마무리

트리 알고리즘을 활용한 최소 공통 조상 (LCA) 문제는 다양한 문제 해결에 사용되는 중요한 알고리즘입니다. Python을 이용하여 LCA를 구현하고 적용하는 방법을 알아보았습니다. 트리 알고리즘에 대한 이해를 통해 다양한 문제에 적용할 수 있도록 하세요!