알고리즘 스터디 15일차

목차

1. 최소 신장 트리 (MST)

2. [최소 신장 트리 실전 문제]

 

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

1. 최소 신장 트리 (MST)

그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리

사용 알고리즘 : 크루스칼, 프림

사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.

따라서 N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다.

에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화 (8일차 참고)

그래프 데이터를 가중치 기준으로 정렬하기 (오름차순 정렬 => 가중치 낮은 에지부터)

가중치 낮은 에지부터 연결 시도하기

전체 노드의 개수가 N개이면 연결한 에지의 개수가 N-1이 될 때까지 연결을 반복, (대표노드가 같다 = 사이클이 생긴다 = 연결불가)

출력

 

 

2. [최소 신장 트리 실전 문제]

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

1197번: 최소 스패닝 트리

 

해설코드

import sys
from queue import PriorityQueue # 우선순위 큐
input = sys.stdin.readline
N, M = map(int, input().split())
pq = PriorityQueue(); # 우선순위 큐 생성
parent = [0] * (N+1) 

# 자신의 부모를 가리키도록 초기화
for i in range(N+1):
    parent[i] = i

for i in range(M):
    s, e, w = map(int, input().split())
    pq.put((w, s, e)) # 입력받은 정보 우선순위 큐에 삽입

# 유니온파인드 (find 함수)
def find(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

# 유니온파인드 (union 함수)
def union(a,b):
    a = find(a)
    b = find(b)
    if a != b:
        parent[b] = a

# 에지 개수와 결과 비용을 초기화
useEdge = 0
result = 0

# 최소신장트리
while useEdge < N-1:
    w, s, e = pq.get() # 오름차순 정렬된 가장 작은 가중치를 우선순위 큐에서 가져옴
    if find(s) != find(e): # 대표노드가 같지않다면(=사이클형성안된다면) union 함수를 통해 연결
        union(s, e)
        result += w # 연결되었다면 결과에 가중치 더함
        useEdge += 1 # 사용한 에지 개수 저장

print(result)

 

 

유니온파인드에 대해 다시 복습하게 되는 과정이었다. 바로 전에 했던 플로이드-워셜과 마찬가지로 이제는 이론보단 코드구조를 외우고 사용하는 부분이 중점인 것 같다. 물론 이론의 이해도 뒷받침되어야 하지만 필요한 코드를 익숙해지기 전까진 찾아서 사용할 수 있으므로 어떤 문제에서 어떤 코드가 사용되는지만 잘 알고 있으면 더 수월할 것 같다.