개발하는데 다 이유가 있겠지

트리 구조

트리는 노드(Node)와 노드들을 연결하는 간선(Edge)으로 연결된 비선형 자료구조

관련 용어

노드(Node)

• 트리를 구성하는 기본 용소
• 노드에는 키 또는 값과 하위 노드에 대한 포인터를 갖고 있음
• 노드 : A, B, C, D, E, F, G, H, I ,J

간선(Edge)

• 노드와 노드 간의 연결선

루트 노드(Root node)

• 트리 구조에서 부모가 없는 최상위 노드
• 루트 노드 : A

부모 노드(Parent node)

• 자식 노드를 가진 노드
• H, I의 부모 노드는 D

자식 노드(Child node)

• 부모 노드의 하위 노드
• 노드 D의 자식 노드는 H, I

형제 노드(Sibling node)

• 같은 부모를 가진 노드
• H, I은 같은 부모를 가진 형제 노드

리프 노드, 외부 노드, 단말 노드(Leaf node)

• 자식 노드가 없는 노드
• 리프 노드 : F, G, H, I, J

가지 노드, 내부 노드, 비단말 노드(Branch node)

• 자식 노드가 1개 이상 있는 노드
• A, B, C, D, E

깊이(Depth)

• 루트에서 어떤 노드까지의 가장 긴 경로의 간선의 수
• 리프 노드의 높이 0
• 루트 노드의 높이 3
• 깊이는 3

레벨(Level)

• 루트에서 어떤 노드까지의 간선의 수

차수(Degree)

• 노드의 자식 수
• 리프 노드의 degree : 0
• 루트 노드의 degree : 2

Path

• 한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서
• A -> H 경로 : A -> B -> D -> H

Path Length

• 해당 경로에 있는 총 노드의 수
• A -> H 경로 길이 : 4

Size

• 자신을 포함한 자손의 노드 수
• 노드 B의 size : 6

Width

• 레벨에 있는 노드 수
• 레벨2 width : 4

Breadth

• 리프 노드의 수
• breadth : 5

Distance

• 두 노드 사이의 최단 경로에 있는 간선의 수
• D -> J의 distance : 3

Order

• 부모 노드가 가질 수 있는 최대 자식의 수
• order 3 : 부모 노드는 최대 3명의 자식을 가질 수 있음

---

특징

• 저장된 데이터를 효과적으로 탐색하기 위해 사용
• 하나의 루트 노드와 0개 이상의 하위트리로 구성
• 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조
• 트리내에 또 다른 트리가 있는 재귀적 자료구조
• 단순 순환(Loop)을 갖지 않고, 연결된 무방향 그래프 구조
• 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조
• 모든 자식 노드는 하나의 부모 노드만 가짐
• 노드가 N개인 트리는 N-1개의 간선을 가짐
  

---

종류

1. 편향 트리(Skew Tree)
   • 모든 노드들이 자식이 한개인 트리
   • 왼쪽 방향으로 자식을 하나씩만 가질 때 Left Skew Tree, 오른쪽 방향으로 자식을 하나씩만 가질 때 Right Skew Tree라고 함
2. 이진 트리(Binary Tree)
   • 각 노드의 차수(자식 노드)가 2 이하인 트리
3. 포화 이진 트리(Full Binary Tree)
   • 리프 노드를 제외한 모든 노드의 차수가 2개로 이루어져 있는 트리
   • 해당 차수에 몇 개의 노드가 있는지 바로 파악 가능
4. 완전 이진 트리(Complete Binary Tree)
   • 모든 노드가 왼쪽 부터 차근차근 생성되는 이진 트리
   • 힙(Heap)은 완전 이진 트리의 일종
5. 이진 탐색 트리(Binary Search Tree, BST)
   • 순서화된 이진 트리
   • 노드의 왼쪽 자식은 부모의 값보다 작은 값을 가져야하며, 노드의 오른쪽 자식은 부모의 값보다 큰 값을 가짐
   • 노드는 중복된 값을 가지지 않음
6. m원 탐색 트리(m-way Search Tree)
   • 최대 m개의 서브 트리를 갖는 탐색 트리
   • 이진 탐색 트리의 확장된 형태로 높이를 줄이기 위해 사용함
7. 균형 트리(Balanced Tree, B-Tree)
   • m원 탐색 트리에서 높이 균형을 유지하는 트리
   • height-balanced m-way tree라고도 함

---

순회 방식

1. 전위 순회(Preorder)

순서 : 루트 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리

2. 중위 순회(Inorder)

순서 : 왼쪽 서브트리 -> 중위 노드 -> 오른쪽 서브 트리

3. 후위 순회(Postorder)

순서 : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 중위 노드

 

[출처]

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

---

알고리즘(최소 스패닝 트리)

크루스칼 알고리즘

Union Find를 알면 더 빠르게 풀이 가능

1. 최소 비용인 간선을 아무거나 선택
2. 선택한 정점에 연결된 정점이 같은 그룹이면 패스
3. 다른 그룹이면 스패닝 리스트에 추가
4. 위의 과정을 반복하면서 모든 정점이 연결되면 종료

---

프림 알고리즘

1. 임의의 정점을 선택
2. 연결된 간선 중 최소 값을 선택(heapq 사용)
3. 선택한 간선과 연결된 정점을 스패닝 리스트에 추가
4. 스패닝 리스트에 담긴 정점의 개수가 n-1개가 될 때까지 반복

풀이

import heapq
import sys

input = sys.stdin.readline

x, y = map(int, input().split())
arr = [[] for _ in range(10001)]
visited_node = [False] * 10001
cost_list = []
result = 0
count = 0
for i in range(y):
    start, end, cost = map(int, input().split())
    arr[start].append((cost, end))
    arr[end].append((cost, start))

# 임의의 점 1번부터 시작
visited_node[1] = True

# 1번에서 비용과 도착지를 꺼내서 그 중 heapq에 / 비용, 출발지, 도착지 순으로 push
for cost, end in arr[1]:
    heapq.heappush(cost_list, (cost, 1, end))

# count가 노드-1개가 될 때까지 반복
while count < x - 1:
    # 힙 큐에서 꺼내서
    cost, start, end = heapq.heappop(cost_list)
    # 방문처리 확인 후
    if visited_node[end]:
        continue
    # 아니면 방문하고 방문처리를 하고 비용을 더하고
    visited_node[end] = True
    result += cost
    count += 1
    # 도착지에서 갈 수 있는 도착지와 비용을 꺼내서 heapq에 추가
    for cost, next in arr[end]:
        if not visited_node[next]:
            heapq.heappush(cost_list, (cost, end, next))
print(result)