개념 신장 트리(Spanning Tree) 모든 정점을 포함하면서 사이클이 없는 그래프 특징 원 그래프의 모든 정점을 포함 간선(node) 수 = 정점 수 - 1 노드 간 사이클을 형성하지 않음 한 그래프 내에서 여러 개의 신장 트리를 가질 수 있음 최소 신장 트리(Minimum Spanning Tree) 간선(node) 가중치의 합이 가장 작은 신장 트리 간선(node) 가중치가 가장 낮은 간선부터 탐색하여 신장트리를 구성하는 방식 대표 알고리즘 : Kruskal 알고리즘, Prim 알고리즘 차이점 Kruskal 알고리즘 : 간선(node)를 중심으로 하여 신장 트리를 구성 Prim 알고리즘 : 정점(spot)을 중심으로 하여 신장 트리를 구성 크루스칼(Kruskal) 알고리즘 가장 작은 가중치를 갖는..

https://www.acmicpc.net/problem/1717 문제 해석 합집합과 같은 집합인지 확인하는 문제로 분리집합(Union-Find)의 대표적인 문제이다. 구현 방법 총 3단계로 나누어 구현 Root를 저장할 배열 초기화 Find 함수 작성 같은 Root를 가지고 있는지 확인( 같은 집합인가 확인) Union 함수 작성 서로 다른 두 집합을 합집합 (Root 를 같게 함) 이미 같으면 할 필요 없음 코드 # 1717 집합의 표현 import sys input = sys.stdin.readline def find(num:int)->int: if parent[num] == num: return num parent[num] = find(parent[num]) return parent[num] de..