IT Studying

https://www.acmicpc.net/problem/1197최소 스패닝 트리란? 스패닝 트리(가장 적은 수의 간선을 이용하여 모든 노드들을 연결한 트리-> n개의 노드면 n-1개의 간선) 중 간선 가중치가 가장 적은 경우최소 스패닝 트리를 구하는 알고리즘에는 프림 알고리즘과 크루스칼 알고리즘이 있다.1. 프림 알고리즘1. 작동 원리- 전체 노드의 집합을 A라 하고, 현재까지 총 방문한 노드들의 집합을 V라 하자- 우선 첫 방문할 노드를 V에 넣는다.- V의 전체 노드들과 A-V의 전체 노드들을 비교해서 A-V에서 가장 거리가 짧은 노드를 선택하여 V에 넣는 것을 반복한다.**코드def prim(W): #W는 2차원배열(각 노드와 거리정보가 들어 있는) n = len(W) - 1 #Vertex의..