[알고리즘] MST 알고리즘

최소 신장 트리 (MST)

• 최소 신장 트리(MST)는 그래프 이론에서 매우 중요한 개념.
• 주어진 그래프에서 모든 정점을 연결하면서, 사용된 간선의 가중치 합이 최소가 되는 트리 구조를 찾는 것이 목표.
• MST는 네트워크 설계, 통신망 구축, 경로 찾기 등 다양한 분야에서 활용됨.

MST의 조건

• 연결성(Connectivity): 그래프의 모든 정점이 서로 연결되어 있어야 합니다.
• 비순환성(Acyclicity): 트리 구조이므로, 사이클이 존재하지 않아야 합니다.
• 최소 가중치(Minimum Weight): 간선의 가중치 합이 최소여야 합니다.

MST 알고리즘: 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘

• MST를 찾는 대표적인 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 있음.

1. 크루스칼(Kruskal) 알고리즘

• 크루스칼 알고리즘은 탐욕 알고리즘(Greedy Algorithm)의 일종으로, 가중치가 가장 작은 간선부터 차례대로 선택하여 MST를 구성.

• 이때, 사이클이 형성되는 간선은 제외.

• 동작 과정:

  • 간선들을 가중치 오름차순으로 정렬.
  • 가중치가 가장 작은 간선부터 선택.
  • 선택한 간선이 이미 선택된 간선들과 사이클을 형성하는지 확인.
  • 사이클이 형성되지 않으면, MST에 포함시킴.
  • 사이클이 형성되면, 해당 간선을 제외.
  • 모든 정점이 연결될 때까지 2~3번 과정을 반복.

• 장점:

  • 구현이 비교적 간단합니다.
  • 희소 그래프(간선이 적은 그래프)에서 효율적입니다.

• 시간 복잡도: O(E log E) (E는 간선의 수)

2. 프림(Prim) 알고리즘

프림 알고리즘 또한 탐욕 알고리즘으로, 시작 정점을 선택한 후, 해당 정점에 연결된 간선들 중에서 가중치가 가장 작은 간선을 선택하여 MST를 확장해 나감.

• 동작 과정:

  • 시작 정점을 선택.
  • 선택된 정점들에 연결된 간선들 중에서 가중치가 가장 작은 간선을 선택합니다.
  • 선택한 간선이 연결하는 새로운 정점을 MST에 추가합니다.
  • 모든 정점이 연결될 때까지 2~3번 과정을 반복합니다.

• 장점:

  • 밀집 그래프(간선이 많은 그래프)에서 효율적입니다.

• 시간 복잡도: O(E log V) (E는 간선의 수, V는 정점의 수) - 우선순위 큐 사용 시

관련 문제 SWEA 1251. 하나로

def union(a, b):
	a = find(parents[a])
	b = find(parents[b])
	if a < b:
		parents[b] = a
	else:
		parents[a] = b
	
	
def find(x):
	if parents[x] != x:
		parents[x] = find(parents[x])
	return parents[x]


def kruskal(N, edges):
	total = 0
	edges.sort(key = lambda x : x[0])
	
	for cost, a, b in edges:
		if find(a) != find(b):
			union(a, b)
			total += cost
	return total
	
T = int(input())

for tc in range(1, T+1):
	N = int(input())
	position_x = list(map(int, input().split()))
	position_y = list(map(int, input().split()))
	parents = [i for i in range(N)]
	edges = []
	E = float(input())
	for i in range(N-1):
		for j in range(i+1, N):
			dx = abs(position_x[j] - position_x[i])
			dy = abs(position_y[j] - position_y[i])
			cost = dx**2 + dy ** 2
			edges.append((cost, i, j))
	
	total_cost = kruskal(N, edges)
	result = total_cost * E
	print(f"#{tc} {result:.0f}")