https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 최소 신장 트리의 유형이다 간선간의 비용은 주어지지 않았기 때문에 비용을 1로 두고 비행기의 종류를 정하게 된다면 어렵지 않게 해결 가능하다. import sys def find_parent(parent,x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def u..

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net import sys def find_union(parent,x): if parent[x] != x: parent[x] = find_union(parent,parent[x]) return parent[x] def union_parent(parent, a,b): a = find_union(parent,a) b = find_union(parent,b) if b< a: parent[a] = b else: parent[b] = a n = int(sys.stdin.readline()) m = in..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net import sys def find_parent(parent,x): if parent[x] != x: parent[x] = find_parent(parent,parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent..

신장 트리는 그래프 알고리즘 문제로 자주 출제되는 유형이다. 기본적으로 신장트리란? 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프이다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다. 그래서 이러한 그래프를 신장 트리라고 부르는 것이다. 크루스칼 알고리즘 우리는 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다. 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결 될 수 있게 도로를 설치하는 경우를 생각해보자. 2개의 도시 A, B를 선택했을 때, 도시 A에서 도시 B로 이동하는 경로가 반드시 존재하도록 도로를 설치하고자 한다. 모든..