[백준] 최소 신장 트리

게시 2024/08/10

By Yu.S.H 6 분읽는 시간

1. 최소 신장 트리?

1.1 개념

최소 신장 트리(MST)는 가중치가 있는 연결 그래프에서 다음의 조건을 만족해야 한다.

연결 그래프가 모든 정점을 포함해야 한다.(모두 이어져 있어야 한다.)
노드들 간의 사이클이 없어야 한다.
사용된 간선들의 가중치 합이 최소가 되어야 한다.

1.2 사용

기본적으로 전체 그래프에서의 최소 비용을 구하는 문제에서 가장 먼저 고려해봐야 한다.

추가로 최소가 되게 간선들을 고르거나, 사이클이 생기지 않게 만든다거나 한다면 높은 확률로 최소 신장 트리를 고려해보자.

1.3 구현방법

최소 신장 트리의 구현엔 서로 다른 2가지 알고리즘이 사용된다.

크루스칼 알고리즘(Kruskal’s Algorithm)
프림 알고리즘(Prim’s Algorithm)

2. 크루스칼 알고리즘(Kruskal’s Algorithm)

크루스칼 알고리즘은 그리디 알고리즘과 유니온 - 파인드를 활용해 MST를 구현한다. 작동 방식을 살펴보자.

2.1 작동 방식

간선들의 정보와 가중치를 입력받은 후, 가중치가 작은 순으로 정렬한다.
가중치가 가장 작은 것부터 선정한 후, 두 노드가 연결되어 있지 않으면 연결한다.
선택한 간선의 두 노드가 서로 연결되어 있을 경우, 사이클 방지를 위해 연결하지 않는다.

2.2 특징

간선이 적은 그래프에서 효율적이다.
간선을 정렬하는데 $O(E log E)$, 유니온 파인드를 사용할때 O(1) 이 사용된다.(E는 간선의 수)

2.3 코드

아래는 크루스칼 알고리즘의 간단한 작동 코드이다.

  
def kruskal():
	while pq:
		cost, a, b = heapq.heappop(pq)
		
		if find(a) != find(b) # 두 노드가 연결되어 있지 않다면 = 같은 부모를 공유하지 않는다면
			union(a, b) # 두 노드 연결
			# 이하 생략
			

기본적으로 union - find 알고리즘에 대해 알고 있어야 한다. union - find를 통해 자연스럽게 사이클이 생성을 방지할 수 있다.

참고사항: 위 코드에선 우선순위 큐를 사용했지만, 파이썬에서 sort()는 우선순위 큐와 시간복잡도가 동일하므로 어떤 방법을 사용해도 좋다.

3. 프림 알고리즘(Prim’s Algorithm)

프림 알고리즘 역시 그리디 알고리즘과 우선순위 큐(여기선 필수)를 사용해 MST를 구현한다.

3.1 작동방식

간선과 가중치를 입력받아 graph에 저장한다.
시작 노드를 정한다.(아무 노드나 골라도 좋다.)
시작 노드와 연결된 노드들을 우선순위 큐에 넣는다.
while 반복문 안에서 이하가 이루어진다.
1. 우선순위 큐에서 가중치가 작은 순서대로 선정한다.
2. 해당 노드를 방문한 적이 없다면 방문 처리한다.
3. 방문한 노드와 연결되어 있는 노드들을 큐에 넣고 큐가 없어질 때 까지 반복한다.

3.2 특징

밀집 그래프(간선이 많은 그래프)에서 효과적이다.
인접 리스트와 우선순위 큐를 이용하면 $O(E logV)$에 구현할 수 있다. (E는 간선의 수, V는 정점의 수)

3.3 코드

이하는 프림 알고리즘의 간단한 코드이다.

  
def prim(start, visited):
    pq = [(0, start)]
    total_weight = 0

    while pq:
        dist_u, u = heapq.heappop(pq)

        if not visited[u]: # 방문한 적이 없다면
            visited[u] = True
            total_weight += dist_u
            for v, w in graph[u]:
                if not visited[v]: # 방문한 적이 없는 노드만 큐에 추가
                    heapq.heappush(pq, (w, v))
		## 이하 생략

3.4 프림 알고리즘이 사이클을 형성하지 않는 이유

프림 알고리즘에서는 다음 정점을 트리에 추가할 때, 반드시 현재 트리에 추가되어 있지 않은 간선만 선택한다. 즉

이미 트리에 추가된 정점이라면, 새로운 간선을 연결할 때 고려 대상이 되지 않는다.
그러므로 이미 추가된 정점 사이의 간선이 생기지 않기 때문에 사이클이 형성되지 않는다.

Algorithm