[백준/파이썬] 1197번 최소 스패닝 트리 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1197번 최소 스패닝 트리
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

가중치가 있는 무방향 그래프에서 모든 정점을 연결하는 최소 비용(최소 스패닝 트리)을 구하는 문제입니다.

코드

import sys;read=sys.stdin.readline
v,e=map(int,read().split())
l=dict()
lines=[list(map(int,read().split()))for _ in range(e)]
for i in range(e):
    lines[i][0]-=1
    lines[i][1]-=1
INT_MAX=2147483648


for line in lines:
    try:l[line[0]]
    except KeyError:l[line[0]]=set()
    l[line[0]].add(line[1])
    try:l[line[1]]
    except KeyError:l[line[1]]=set()
    l[line[1]].add(line[0])

def detectMin(d, c):
    m=INT_MAX
    r=-1
    for i in range(len(d)):
        if m > d[i] and i not in c:
            m = d[i]
            r=i
    if r!=-1: c.add(r)
    return r

def w(u,v):
    for i in range(len(lines)):
        if lines[i][0]==u and lines[i][1]==v or\
        lines[i][0]==v and lines[i][1]==u :
            return lines[i][2]

def prim(r=0):
    global v
    tree=dict()
    d=[INT_MAX for _ in range(v)]
    d[r]=0
    c=set()
    cnt=1
    while len(c)<v:
        u = detectMin(d,c)
        for v in l[u]:
            wuv=w(u,v)
            if v not in c and wuv<d[v]:
                d[v]=wuv
                tree[v]=u
                cnt+=1
    return sum(d)
print(prim())

설명

프림(Prim) 알고리즘으로 MST를 구성합니다.

• d[i]: 트리에 정점 i를 붙일 수 있는 현재 최소 간선 가중치
• c: 이미 트리에 포함된 정점 집합
• 매 단계마다 d가 가장 작은 정점을 선택해 확장

최종적으로 d 합이 최소 스패닝 트리의 총 가중치가 됩니다.

---

• 백준 문제풀이 전체 목록 보기

---