백준 1197번. 최소 스패닝트리 (Python)

Wjong·2023년 4월 13일
0

baekjoon

목록 보기
17/17

문제 : https://www.acmicpc.net/problem/1197

풀이

최소 스패닝 트리를 이용해 푸는 문제이다.
크루스칼 알고리즘을 이용했다.

  • 노드가 어떤 노드와 연결되어 있는지 정보를 담을 nodes 배열과, 어떤 노드가 연결되어 있고 가중치가 몇인지 담을 배열 li를 준비한다.
  • 두가지 함수를 준비한다.
    - find함수는 노드a가 연결되어 있는 루트노드를 찾아 리턴한다.
    - union함수는 a와 b의 루트노드가 다를 경우, 연결하여 준다.
  • li배열을 가중치 오름차순으로 정렬해 준다.
  • li배열을 순회하면서 a와 b의 루트노드가 다를경우, 결과값가중치에 v를 더해주고, a와 b를 union 해준다.
  • 마지막으로, 결과값가중치를 출력
import sys
input=sys.stdin.readline

V,E=map(int,input().split())
li=[]
cnt=0
weight=0
nodes=[i for i in range(V+1)] # 노드의 수만큼 배열 생성

for i in range(E): #간선정보 입력
    A,B,C=map(int,input().split()) # A와 B가 가중치 C로 연결
    li.append([A,B,C])

def find(a): # a노드의 루트노드를 찾는 과정
    if nodes[a]==a:
        return a
    else:
        nodes[a]=find(nodes[a])
        return nodes[a]
    
def union(a,b): # a와 b노드를 합치는 과정
    a=find(a)
    b=find(b)
    if a!=b: # a와 b의 루트노드가 다른 노드일 경우
        if a<b: # a의 루트노드가 b보다 작을경우
            nodes[b]=a # a의 아래에 b를 단다
        else:
            nodes[a]=b
li.sort(key=lambda x:x[2]) # 가중치 오름차순으로 정렬
i=0
while cnt<V-1:
    a,b,v=li[i][0],li[i][1],li[i][2]
    if find(a)!=find(b):
        cnt+=1
        weight+=v
        union(a,b)
    i+=1
print(weight)
profile
뉴비

0개의 댓글