[백준] 1197번 최소 스패닝 트리 (프림, 크루스칼)

사용 언어 - Python3, PyPy3

문제 -  1197번 최소 스패닝 트리

Minimum Spanning Tree 최소한으로 뻗어나가는 트리

- 프림  = 다익스트라 이용해서 MST 구하는 문제

- 크루스칼 = 유니온파인드 이용해서 MST 구하는 문제

 

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

1197번: 최소 스패닝 트리

  

정답

최소 스패닝 트리 알고리즘

트리의 기본 조건 : 사이클 발생 X

 

 

방법1. 프림

다익스트라를 이용해서 방문한 곳인지 확인한다.

1. 방문하면서 링크 정보를 저장한다.

2. 방문한 곳은 다시 연결하지 않는다.

 

상세 설명

다익스트라 = 힙 이용한 탐색 import heapq

노드&가중치를 graph에 input

이때 가중치를 기준으로 heappop() 을 통해 꺼내줘야 하기 때문에 가중치를 앞으로 저장한다. graph[a] = [weight, b]

q = [[0,1]] weight = 0, node = 1 에서 출발

q 가 없어질 때까지 반복한다. 모든 정점을 다 돌았다면, break 멈춘다.

weight, node = heapq.heappop(q)

만약 node를 방문하지 않았다면, 다음 노드 방문해준다. heaq.heappush(q,nxt)

 

# 프림
import heapq
v,e = map(int, input().split()) # 정점의 개수, 간선의 개수
graph = [[] for _ in range(v+1)]
visited = [0 for _ in range(v+1)]

for _ in range(e):
    a,b,c = map(int,input().split()) # 정점 a,b 가중치 c
    graph[a].append([c,b])
    graph[b].append([c,a])

# 다익스트라 탐색
answer = 0
cnt = 0
q = [[0,1]] # 1에서 출발할거다. 가중치 없이
while q: # q가 아무것도 없어질 때까지
    if cnt == v:
        break
        
    weight, node = heapq.heappop(q) # 최소비용 꺼내주기
    if visited[node] == 0:
        visited[node] = 1        
        answer += weight
        cnt += 1
        for nxt in graph[node]:
            heapq.heappush(q,nxt)
print(answer)

 

 

 

방법2. 크루스칼

유니온파인드를 이용해서 같은 집합인지 확인한다.

1. 모든 링크를 한번에 가져온다.

2. 링크를 연결하면서 같은 집합으로 만들어준다.

3. 만약에 이미 같은 집합이라면 연결하지 않는다.

 

상세 설명

모든 링크를 한번에 link 리스트에 저장한 후, 가중치를 기준으로 오름차순 정렬해준다.

디폴트로 자기 자신을 부모로 갖는 부모 리스트를 생성.

유니온 최적화를 할 것이기 때문에 rank 리스트를 생성.

a = _find(a), b = _find(b) a와 b 노드의 부모를 찾고

부모가 다르다면, _union(a,b) 같은 집합으로 만들기

부모가 같다면, 같은 집합이기 때문에 무시(트리는 사이클 없어야 하기 때문)

 

# 크루스칼
# union 최적화
def _find(x):
    while par[x] != x:
        x = par[x]
    return x

def _union(a,b):
    a = _find(a)
    b = _find(b)
    
    if a == b:
        return
    
    if rank[a] < rank[b]:
        par[a] = b
    elif rank[b] < rank[a]:
        par[b] = a
    else:
        par[a] = b
        rank[b] += 1

v,e = map(int, input().split()) # 정점의 개수, 간선의 개수
link = [list(map(int,input().split())) for _ in range(e)] # 모든 링크 가져오기
link.sort(key=lambda x:x[2])# 가중치 기준으로 정렬
par = [i for i in range(1_000_001)] # 부모
rank = [0 for _ in range(1_000_001)] # union 최적화

answer = 0
for i in range(e):
    a = link[i][0]
    b = link[i][1]
    weight = link[i][2]
    
    # 같은 부모인지 찾기    
    a = _find(a)
    b = _find(b)
    # 부모 같지 않을 때만 합해주기
    if a != b:
        _union(a,b)
        answer += weight
    else:
        continue
        
print(answer)

 

 

레퍼런스

• 깃허브 정답

프림

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/1197_%EC%B5%9C%EC%86%8C%EC%8A%A4%ED%8C%A8%EB%8B%9D%ED%8A%B8%EB%A6%AC.py

 

크루스칼

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/1197_%EC%B5%9C%EC%86%8C%EC%8A%A4%ED%8C%A8%EB%8B%9D%ED%8A%B8%EB%A6%AC1.py