728x90
https://school.programmers.co.kr/learn/courses/30/lessons/42861
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분석
[1197번] 최소 신장 트리(MST, 크루스칼, 프림, 유니온파인드)
1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이
karla.tistory.com
풀이
from queue import PriorityQueue
def solution(n, costs):
answer = 0
q = PriorityQueue()
# 유니온파인드
arr = [0]*n # 인덱스 리스트
for i in range(n):
arr[i]=i
for s,e,cost in costs: # 에지 리스트
q.put((cost,s,e))
q.put((cost,e,s))
def find(a): # 대표노드 찾기
if a == arr[a]:
return a
else:
arr[a] = find(arr[a])
return arr[a]
def union(a, b):
a = find(a)
b = find(b)
if a != b:
arr[b] = a
useEdge = 0
while useEdge<n-1:
w,s,e=q.get()
if find(s) != find(e):
union(s, e)
answer+=w
useEdge+=1
return answer def solution(n, costs):
answer = 0
edges = sorted([(x[2], x[0], x[1]) for x in costs])
arr = [i for i in range(n)]
def find(a):
if a == arr[a]:
return a
else:
arr[a] = find(arr[a])
return arr[a]
useEdge = 0
for w, s, e in edges:
if find(s) != find(e):
arr[find(s)]=e
answer+=w
useEdge += 1
if useEdge == n-1:
break
return answer728x90