[백준]1197 최소스패닝트리

1. 풀이

최소스패닝트리(MST)문제. 크루스칼 알고리즘을 사용한다.

사이클을 확인하기 위해 유니온파인드를 이용해아햐며, 이때 dfs(or bfs)를 사용하면 시간초과가 난다.

​

2. 소스코드

(1) dfs,시간초과

import heapq
from collections import deque
def isCycle(L):
    visited=[-1 for i in range(V+1)]
    stack=deque([L[0][0]])
    while(stack):
        temp=stack.pop()
        # 스택에 있으면 싸이클
        if temp in stack:
            return True
        visited[temp]=1
        for n1,n2 in L:
            if n1==temp and visited[n2]==-1:
                stack.append(n2)
            elif n2==temp and visited[n1]==-1:
                stack.append(n1)
    return False

V,E=map(int,input().split())
edge=[]
for i in range(E):
    A,B,C=map(int,input().split())
    heapq.heappush(edge,[C,A,B])

kruscal=[]
ans=0
#크루스칼 시작
while(len(kruscal)!=V-1):
    cost,node1,node2=heapq.heappop(edge)
    kruscal.append([node1,node2])
    if isCycle(kruscal):
        kruscal.pop()
    else:
        ans+=cost
print(ans)

 

(2) 유니온파인드, 통과

import heapq

def find(x):
    if parent[x]==x:
        return x
    else:
        parent[x]=find(parent[x])
        return parent[x]
def union(x,y):
    x=find(x)
    y=find(y)
    if (x!=y):
        parent[x]=y
def isCycleUnion(node1,node2):
    # 사이클이면
    if find(node1)==find(node2):
        return True
    # 사이클 아니면
    else:
        union(node1, node2)
        return False
V,E=map(int,input().split())
parent = [i for i in range(V + 1)]
edge=[]
for i in range(E):
    A,B,C=map(int,input().split())
    heapq.heappush(edge,[C,A,B])

edgeNum=0
ans=0
#크루스칼 시작
while(edgeNum!=V-1):
    cost,n1,n2=heapq.heappop(edge)
    if not isCycleUnion(n1,n2):
        ans+=cost
        edgeNum+=1

print(ans)