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

개념 그래프 이론으로, 상호 배타적 집합(서로소집합:Disjoint-Set) 알고리즘이라고도 부름 주로 크루스칼(Krusckal) 알고리즘에서 사용하며, 순환하지 않는 트리 를 만들기 위해 사용 단계별로 이해하기 만약 아래 표와 같이 4개의 노드를 가진 서로소 집합이 있다면, 노드 번호 1 2 3 4 대표 번호 1 2 3 4 1번과 2번이 같은 집합이라면? 대표번호를 변경하여 같은 집합을 표현할 수 있음 Union 결과 노드 번호 1 2 3 4 대표 번호 1 1 3 4 아래 표와 같이 있을 때 2번은 어떤 집합에 있는지 알 수 없을까? 노드 번호 1 2 3 4 대표 번호 1 3 4 1 노드 번호를 따라가며 확인할 수 있음 2번 👉 3번 👉 4번 👉 1번 (모두 같은 집합) Find 다른 표현 노드 번호 ..

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..