728x90 최소신장트리3 [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. [Algorithm] 최소 신장 트리 (MST) 신장 트리 n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanning Tree) 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 Prim Algorithm 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 임의 정점 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점 선택 모든 정점이 선택될 때 까지 반복 ''' 6 11 0 1 32 0 2 31 0 5 60 0 6 51 1 2 21 2 4 46 2 6 25 3 4 34 3 5 18 4 5 40 4 6 51 ''' def find_MST(s): key[s] = 0 # 정점.. 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