[파이썬] 1197. 최소 스패닝 트리

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력 1 

3 3

1 2 1

2 3 2

1 3 3

예제 출력 1 

3

 

 

💜 나의 풀이

 

import sys, heapq
input=sys.stdin.readline
V, E=map(int, input().split())  #정점, 간선 개수
visited=[0]*(V+1)
lst=[[] for _ in range(V+1)]
ans=0

for e in range(E) :
    A, B, C=map(int, input().split())   # 노드, 노드, 가중치
    lst[A].append((C, B))
    lst[B].append((C, A))

que=[(0,1)]     
while que :
    node=heapq.heappop(que)
    if not visited[node[1]] :
        visited[node[1]]=1
        ans+=node[0]
        for n in lst[node[1]] :
            heapq.heappush(que, n)

print(ans)

 

우선순위큐와 bfs 탐색

인덱스=기준노드, 값=(가중치, 기준노드와 연결된 노드)인 노드가 양방향으로 연결된 lst 생성

가중치가 작은 것부터 뽑아서 시작하려고 했는데 que=heapq.heappop(lst)를 하면 que가 null이 되어서 while문이 실행이 안됨...

que에 [(가중치, 임의의 시작 노드 번호}]를 줬다.

while문에서 구현은 bfs랑 같음

pop하고 방문한 적 없으면 visited에 1 넣고, 가중치를 더한 후 연결 된 노드를 que에 추가했다.

que에 원소가 있을때까지 이 과정 반복

 

# 실패(시간 초과)
import sys
input=sys.stdin.readline

V, E=map(int, input().split())    # 정점, 간선 개수
edge=[list(map(int, input().split())) for e in range(E)]
edge.sort(key=lambda x:x[2])    # 가중치가 작은 순으로 정렬
routes=set([edge[0][0]])
ans=0
while len(routes) != V :
    for i, cost in enumerate(edge) :
        if cost[0] in routes and cost[1] in routes :
            continue
        if cost[0] in routes or cost[1] in routes :
            routes.update([cost[0], cost[1]])
            ans+=cost[2]
            edge[i]=[-1, -1, -1]
            break
print(ans)

 

모든 정점들을 사이클 없이 최소 가중치 합을 가지도록 연결한다.

 

# 실패
import sys, heapq
from collections import deque
input=sys.stdin.readline
V, E=map(int, input().split())  #정점, 간선 개수
visited=[0]*(V+1)
lst=list()
ans=0

for e in range(E) :
    A, B, C=map(int, input().split())   # 노드, 노드, 가중치
    lst.append([C, A, B])

que=deque([heapq.heappop(lst)])      # 가중치가 작은 것부터 시작
while que :
    node=que.popleft()
    if not visited[node[1]] :
        visited[node[1]]=1
        ans+=node[0]
        heap=heapq.heappop(lst)
        if not visited[heap[1]] :
            que.append(heap)

print(ans)

 

heap을 이용해서 가중치가 작은 순서대로 노드를 뽑을려고 했다.

가중치가 작은 순으로 que에 추가하고 방문한적 없는 노드면 가중치의 합 ans에 더했다.

이렇게 하면 트리의 연결은 무시하는 것......

 

 

👧 다른 사람 풀이

 

# https://velog.io/@coding_egg/%EB%B0%B1%EC%A4%80-1197%EB%B2%88-%EC%B5%9C%EC%86%8C-%EC%8A%A4%ED%8C%A8%EB%8B%9D-%ED%8A%B8%EB%A6%AC-python-%ED%8C%8C%EC%9D%B4%EC%8D%AC
from sys import stdin

read=stdin.readline
V, S=map(int, read().split())	# 정점, 간선의 개수

edge=[]
for _ in range(S) :
    a, b, w=map(int, read().split())	# 정점, 정점, 가중치
    edge.append((w, a, b))

edge.sort(key=lambda x : x[0])	# 가중치를 중심으로 오름차순 정렬

parent=list(range(V+1))

def union(a, b) :
    a=find(a)
    b=find(b)

    if b < a :
        parent[a]=b
    else :
        parent[b]=a

def find(a) :
    if a == parent[a] :
        return a
    parent[a]=find(parent[a])   # 경로 압축
    return parent[a]

sum=0
for w, s, e in edge :
    if find(s) != find(e) :
        union(s, e)
        sum+=w

print(sum)

 

크루스칼 알고리즘, 유니온 파인드를 이용한 풀이

 

 

# https://velog.io/@jajubal/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EB%B0%B1%EC%A4%80-1197-%EC%B5%9C%EC%86%8C-%EC%8A%A4%ED%8C%A8%EB%8B%9D-%ED%8A%B8%EB%A6%AC
from heapq import heappush, heappop
import sys
input=sys.stdin.readline

def prim(start, weight) :
    visit=[0]*(V+1)     # 정점 방문 처리
    q=[[weight, start]]     # 힙 구조를 사용하기 위해 가중치를 앞에 둠
    ans=0   # 가중치 합
    cnt=0   # 간선의 개수
    while cnt < V :     # 간선의 개수 최대는 V-1
        k, v=heappop(q)
        if visit[v] : continue # 이미 방문한 정점이면 지나감
        visit[v]=1      # 방문안했으면 방문처리
        ans+=k      # 해당 정점까지의 가중치를 더해줌
        cnt+=1      # 간선의 갯수 더해줌
        for u, w in G[v] :  # 해당 정점의 간선정보를 불러옴
            heappush(q, [w, u])     # 힙에 넣어줌
    return ans

V, E=map(int, input().split())
G=[[] for _ in range(V+1)]
for _ in range(E) :
    u, v, w=map(int, input().split())
    G[u].append([v, w])
    G[v].append([u, w])

print(prim(1, 0))

 

Prim 알고리즘 사용

인덱스=노드, 값=[연결된 노드, 가중치]인 리스트 G 생성

heap을 사용해서 가중치가 작은 순서대로 pop한다.

힙에 해당 노드와 연결된 노드를 push한다.

 

 

 

문제 출처 👉 백준