728x90 크루스칼2 [BOJ/Python] 1197. 최소 스패닝 트리 📌 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 📌 문제 접근 방법 크루스칼 알고리즘을 사용해서 구현하였다. 가중치를 기준으로 오름차순 정렬한 후, 정렬된 순서대로 간선을 선택하여 사이클이 만들어지지 않는다면 (간선에 연결된 노드 2개가 같은 집합이 아니라면) 노드를 연결하고 가중치를 total에 더해준다. 📌 코드 # 백준 1197 최소 스패닝 트리 def find_set(x): if x.. 2021. 10. 21. [SWEA/Python] 5249. 최소 신장 트리 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 크루스칼 알고리즘을 사용해서 풀었다. 간선을 가중치를 기준으로 내림차순 정렬을 해준다. 노드1, 노드2의 조상 노드가 다르다면 사이클이 만들어지지 않으므로 연결해준다. 3번의 과정을 반복하며 가중치를 더해서 출력해준다. 📌 코드 import sys sys.stdin = open('input.txt') def find_set(x): if x != parents[x]: parents[x] = find_set(parents[x]) return parents[x] def.. 2021. 10. 14. 이전 1 다음 728x90