최소 비용 연결
-
백준 1922 네트워크 연결Algorithm/BOJ 2021. 4. 30. 17:04
출처: www.acmicpc.net/problem/1922 분류: kruskal 접근방식 최소 비용으로 모든 간선을 연결할 수 있는 경우를 찾는 크루스칼 알고리즘을 연습해볼 수 있는 문제였습니다. 별다른 트릭은 없어서 크루스칼 알고리즘을 이해하고 있다면 쉽게 해결할 수 있습니다. 간선을 정렬하고 사이클이 생기지 않도록 합쳐주면서 간선의 개수를 노드-1개까지 선택해주면 됩니다. 사이클은 union-find 알고리즘으로 확인할 수 있습니다. 해결방법 let n = Int(readLine()!)! var graph = [[Int]](repeating: [Int](repeating: 10001, count: n+1), count: n+1) var unionTable = [Int]() for i in 0...n ..