[백준] #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를 해 최소한의 노드만 확인해 주는 것으로 해결했다.
Author And Source
이 문제에 관하여([백준] #1647 Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@enchantee/백준-1647-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)