[백준] #1647 Python

백준 1647번 파이썬

https://www.acmicpc.net/problem/1647

아이디어

https://m.blog.naver.com/ndb796/221230994142

크루스칼 알고리즘(최소 신장 트리): 가장 적은 비용으로 모든 노드를 연결할 때 사용하는 알고리즘

• 간선 정보를 오름차순으로 정렬한 뒤 비용이 적은 간선부터 차례차례 그래프에 포함 -> 노드와 간선 정보를 tuple로 묶어서 heapq에 저장(heappop()을 해줄 때 자동으로 가장 적은 비용의 간선 정보부터 확인 가능)
• 사이클을 형성하지 않아야 한다 -> union-find 알고리즘

전체코드

import sys
import heapq
input = sys.stdin.readline


## Union_find 알고리즘 -> 사이클 확인해주려고!
def getParent(parent, x):
    if parent[x] == x:
        return x
    else:
        parent[x] = getParent(parent, parent[x])
        return parent[x]

def unionParent(parent, a, b):
    a = getParent(parent, a)
    b = getParent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def findParent(parent, a, b):
    a = getParent(parent, a)
    b = getParent(parent, b)
    if a == b: # 이미 같은 부모에 속해 있다 = 서로 연결돼 있다.
        return 1
    else:
        return 0


N, M = map(int, input().split())
edge = []
for i in range(M):
    a, b, c = map(int, input().split())
    heapq.heappush(edge, (c, a, b))

cycle_check = [0] * (N+1)
for i in range(1, N+1):
    cycle_check[i] = i

edge_lst = []
for _ in range(M):
    if len(edge_lst) == N-1:
        break
    line, node_a, node_b = heapq.heappop(edge)
    if not findParent(cycle_check, node_a, node_b):
        edge_lst.append(line)
        unionParent(cycle_check, node_a, node_b)
    else:
        continue

edge_lst.pop()
ans = sum(edge_lst)
print(ans)   

느낀점

처음에 모든 간선 정보를 다 보게 코드를 짜서 시간 초과가 나왔다 -> 간선 확인할 때에 edge_lst의 길이를 확인해주는 조건을 넣어 이미 모든 노드를 리스트에 추가해 주었으면 break를 해 최소한의 노드만 확인해 주는 것으로 해결했다.