목록최소스패닝트리 (1)
이숭간 공부기록
[백준] 1922번 파이썬 _ 네트워크
https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제유형 : 최소스패닝트리 (MST) 문제풀이 : 변형없는 전형적인 최소스패닝트리 문제이다. 프림과 크루스칼 알고리즘을 쓸 수 있는데 구현이 좀더 쉬운 크루스칼 알고리즘을 이용했다. 크루스칼 알고리즘에서는 서로소집합개념인 유니온파인드 개념을 알고있어야한다. 정답코드 : import sys input = sys.stdin.readline #크루스칼알고리즘 # 비용을 오름차순으로 정렬하고 # 사이클이 발생하면 추가하지않고, 사이클이 발생하지 않으면 추가한다. # 특정 원소가 속한 집합을 찾..
알고리즘/백준
2021. 8. 16. 01:25