Kruskal

[백준] 1922. 네트워크 연결 - Python

[Gold IV] https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 기본적인 MST(Minimum Spanning Tree) 문제. Kruskal 알고리즘을 통해 MST를 구현하였다. 응용된 것 없이 MST를 구현하기만 하면 되는 문제이므로 설명은 생략. AC. from collections import deque # input N = int(input()) M = int(input()) root = {i: i for i in range(1, N+1)} edges = [] for _ in range(M): a, b, c = map..

[프로그래머스] 42861. 섬 연결하기

https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 최소 신장 트리 (MST)의 Kruskal 알고리즘을 이용하여 풀었음. 우선 cost에 따라 오름차순으로 배열 정렬. vertex의 연결을 저장하고, Union-Find에 이용할 dicionary를 하나 생성하고, union-find를 구현(find, union func.) Kruskal 알고리즘을 적용해 cost가 낮은 순으로 정렬한 edge들에 대해 순회하며 사이클이 생기지 않도록 간선(..