Kruskal 알고리즘 2

백준 1922번 - 네트워크 연결

백준 1922번 - 네트워크 연결https://www.acmicpc.net/problem/1922 문제도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다.하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다.그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다.(a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다.이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한..

아카이빙/BOJ 2017.08.10

Python으로 알고리즘 공부 12. 최소 신장 트리 - Kruskal 알고리즘

최소 신장 트리 (Minimum Spanning Tree) 최소신장트리?신장트리란, 사이클을 형성하지 않고 그래프의 모든 정점(V)이 간선(E)으로 연결되어 있는 것최소신장트리란 최소한의 비용으로 신장트리를 형성하는 것 Kruskal's Algorithm모든 정점을 독립적인 집합으로 만든다.모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다.시간 복잡도는 ​ Python Codeparent = {} rank = {} ​ # 정점을 독립적인 집합으로 만든다. def make_set(v): parent[v] = v rank[v] = 0 ​ # 해당 정점의 최상위 정점을 찾는다. def find(v):..

아카이빙 2017.07.20