딥러닝 공부방

백준 1647번 도시 분할 계획 www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 파이썬 코드 크루스컬 알고리즘을 사용하여 그래프를 MST로 만들었습니다. 또한 두 개의 집합으로 분리해야 하므로 MST의 간선 개수가 N-2가 될 때 중지되도록 구현했습니다. import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N, M = map(int,input().spli..

크루스컬 알고리즘(Kruskal Algorithm) 가중치가 있는 무방향 그래프를 최소 신장 트리로 만드는 알고리즘입니다. 최소 신장 트리는 가중치가 최소인 순환이 없는 무방향 그래프 입니다. 순환이 없으므로 간선 수는 정점 수 - 1이 됩니다. 크루스컬 알고리즘은 Greedy Algorithm에 속하며, 매 번 순환이 되지 않도록 가중치가 가장 적은 다음 간선을 선택합니다. 시잔복잡도 O(ElogN) 작동 원리 (1) 간선을 가중치를 기준으로 정렬합니다. (2) 가장 가중치가 작은 간선(u, v)을 선택합니다. (3) union find 알고리즘을 통해 u와 v를 병합합니다. (4) union find 알고리즘은 각 정점을 분리 집합으로 만들고 서로 다른 집합에 속해있는 정점을 하나의 집합으로 병합합니..