트리

• 노드와 에지로 연결된 그래프의 특수한 형태

트리의 특징

• 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.
• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.
• 트리의 부분 트리 역시 트리의 모든 특징을 따른다.
• 트리에서 임의의 두 노드를 이어주는 경로는 유일하다.

트리의 구성 요소

구성 요소	설명
노드	데이터의 index와 value를 표현하는 요소
에지	노드와 노드의 열결 관계를 나타내는 선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드
서브 트리	전체 트리에 속한 작은 트리

코딩 테스트에서 tree

• 그래프로 푸는 tree
  • 인접 리스트 -> DFS, BFS
• tree만을 위한 문제
  • 이진트리 & 세그먼트 트리(index tree) & LCA(최소 공통 조상)
    • 1차원 배열로 tree 표현
      • 부모 노드로 이동 : index / 2

크루스칼 알고리즘

• 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용
• 모든 정점을 포함하고 사이클이 없는 연결 선 ➡️ 가중치의 합이 최소

백준 1197

import sys

input = sys.stdin.readline


def find(n):
    if parent[n] != n:
        parent[n] = find(parent[n])
    return parent[n]


def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


V, E = map(int, input().split())
tree = [tuple(map(int, input().split())) for _ in range(E)]
parent = list(range(V + 1))

tree.sort(key=lambda x: x[2])

ans = 0
for a, b, c in tree:
    if find(a) != find(b):
        union(a, b)
        ans += c

print(ans)