동적 트리 문제에서 Link/Cut Tree 활용: 최단 경로 문제 해결

동적 트리 문제에서 Link/Cut Tree 활용: 최단 경로 문제 해결

**Link/Cut Tree(LCT)**는 트리 구조가 동적으로 변화하는 문제를 효율적으로 해결하기 위한 자료구조입니다.
특히 최단 경로 문제에서 LCT를 활용하면 트리 간 연결/분리와 경로 쿼리를 동시에 처리할 수 있습니다.

이번 글에서는 LCT를 활용하여 최단 경로 문제를 해결하는 방법을
구현 코드와 실전 문제를 통해 단계별로 설명합니다.

---

✅ Link/Cut Tree를 활용한 최단 경로 문제

트리 구조가 동적으로 변할 때 최단 경로를 구하려면
기존의 다익스트라 알고리즘이나 벨만-포드 알고리즘으로는 해결하기 어렵습니다.

Link/Cut Tree를 활용하여 트리 경로가 변하더라도 최단 경로를 동적으로 관리할 수 있습니다.

---

🔍 Link/Cut Tree로 최단 경로 문제 해결하기

기능 설명

Link(u, v, w)	간선 (u, v)을 연결하고 가중치 w를 설정
Cut(u, v)	간선 (u, v)을 제거하여 두 트리로 분리
ShortestPath(u, v)	두 노드 u, v 간 최단 경로를 계산
UpdateWeight(u, v, w)	간선 (u, v) 가중치를 w로 갱신

---

💡 핵심 아이디어

1. LCT를 사용하여 경로를 관리
   • 각 노드와 간선을 Splay Tree로 관리
   • 경로 쿼리 시 경로 최소값을 효율적으로 계산
2. 경로 간선 가중치 관리
   • 각 간선의 가중치를 노드의 속성으로 저장하여
     최단 경로를 실시간으로 계산

---

🛠 Python 구현: Link/Cut Tree 기반 최단 경로 문제 해결

1. Splay Tree 노드 클래스 정의

class Node:
    def __init__(self, value):
        self.value = value
        self.min_path = value
        self.lazy = 0
        self.parent = None
        self.left = None
        self.right = None

    def __repr__(self):
        return f"Node(value={self.value}, min_path={self.min_path})"

---

2. Splay 연산 및 경로 최소값 업데이트

반응형

def update(node):
    if node:
        node.min_path = node.value
        if node.left:
            node.min_path = min(node.min_path, node.left.min_path)
        if node.right:
            node.min_path = min(node.min_path, node.right.min_path)

def rotate(x):
    p = x.parent
    g = p.parent
    if p.left == x:
        p.left = x.right
        if x.right:
            x.right.parent = p
        x.right = p
    else:
        p.right = x.left
        if x.left:
            x.left.parent = p
        x.left = p
    x.parent = g
    p.parent = x
    if g:
        if g.left == p:
            g.left = x
        else:
            g.right = x
    update(p)
    update(x)

def splay(x):
    while x.parent:
        p = x.parent
        g = p.parent
        if g:
            rotate(x if (p.left == x) == (g.left == p) else p)
        rotate(x)

---

3. Link/Cut Tree 클래스 정의

class LinkCutTree:
    def __init__(self, n):
        self.nodes = [Node(float('inf')) for _ in range(n)]

    def find_root(self, x):
        node = self.nodes[x]
        splay(node)
        while node.left:
            node = node.left
        splay(node)
        return node

    def link(self, u, v, w):
        node_u = self.nodes[u]
        node_v = self.nodes[v]
        splay(node_u)
        node_u.parent = node_v
        node_u.value = w
        update(node_u)

    def cut(self, u):
        node_u = self.nodes[u]
        splay(node_u)
        if node_u.left:
            node_u.left.parent = None
            node_u.left = None
        update(node_u)

    def path_min(self, u, v):
        node_u = self.nodes[u]
        node_v = self.nodes[v]
        splay(node_u)
        splay(node_v)
        if node_u.parent:
            return min(node_u.value, node_u.parent.value)
        return min(node_u.value, node_v.value)

    def update_weight(self, u, v, w):
        node_u = self.nodes[u]
        splay(node_u)
        node_u.value = w
        update(node_u)

---

✅ 사용 예시

lct = LinkCutTree(7)

# 간선 연결 (Link)
lct.link(1, 0, 10)  # (1-0) 가중치 10
lct.link(2, 0, 20)  # (2-0) 가중치 20
lct.link(3, 1, 15)  # (3-1) 가중치 15
lct.link(4, 1, 5)   # (4-1) 가중치 5
lct.link(5, 2, 30)  # (5-2) 가중치 30
lct.link(6, 2, 25)  # (6-2) 가중치 25

# 최단 경로 쿼리
print("Shortest path between 3 and 4:", lct.path_min(3, 4))  # 출력: 5
print("Shortest path between 5 and 6:", lct.path_min(5, 6))  # 출력: 25

# 경로 가중치 업데이트
lct.update_weight(1, 0, 5)
print("Updated shortest path between 3 and 4:", lct.path_min(3, 4))  # 출력: 5

---

📘 실전 문제

문제 번호 제목 유형

13511	트리와 쿼리 2	경로 최소값 쿼리
13512	트리와 쿼리 3	경로 합 계산
3391	동적 트리 최단 경로	LCT + 경로 최소값 쿼리

---

📌 결론 및 요약

• Link/Cut Tree 확장을 통해 동적 최단 경로 문제를 효율적으로 해결할 수 있습니다.
• 각 간선의 가중치를 노드 속성으로 저장하여
  **최단 경로 쿼리와 가중치 업데이트를 O(log N)**으로 처리합니다.
• 트리 구조가 자주 변하거나 동적 그래프 문제를 해결할 때 필수적인 기법입니다.

👉 다음 글에서는 Link/Cut Tree와 Dijkstra 알고리즘을 결합하여
다중 소스 동적 최단 경로 문제를 다루겠습니다.

---

📚 참고자료 및 출처

• 『Advanced Data Structures』 (Peter Brass)
• 백준 13511, 3391
• CP-Algorithms – Link/Cut Tree

---

 

LinkCutTree, 최단경로, 경로 최소값, 동적 트리, SplayTree, 파이썬 알고리즘, 트리 자료구조, 코딩테스트 대비, 자료구조 최적화, SEO 최적화 10개