알면 도움되는 코딩 테스트 유형: 14) #MST

• 이번 글에서는 최소 스패닝 트리(Minimum Spanning Tree)에 대한 개념과 코딩 테스트에서 이 문제를 해결하는 방법에 대해 알아보겠습니다. 최소 스패닝 트리는 그래프 이론의 주요 주제 중 하나입니다.

 

최소 스패닝 트리(Minimum Spanning Tree)의 개념

 

• 최소 스패닝 트리란, 가중치가 있는 연결 그래프에서 모든 정점을 가장 적은 비용으로 연결하는 부분 그래프입니다. 주어진 그래프의 모든 정점을 포함하면서 사이클이 없고, 가중치의 합이 최소인 부분 그래프를 찾는 것이 목표입니다.

 

최소 스패닝 트리에 사용되는 알고리즘

 

• 크루스칼 알고리즘: 간선들을 가중치 순으로 정렬한 후, 사이클을 형성하지 않으면서 간선을 추가하여 최소 스패닝 트리를 만듭니다.

 

1. 모든 간선을 가중치 순으로 정렬합니다.
2. 사이클을 형성하지 않으면서 가장 작은 가중치의 간선부터 선택합니다.
3. 선택한 간선을 최소 스패닝 트리에 추가합니다.
4. 모든 정점이 연결될 때까지 2-3 단계를 반복합니다.

# Union-Find 자료구조 구현
def find(parents, x):
    if parents[x] != x:
        parents[x] = find(parents, parents[x])
    return parents[x]

def union(parents, ranks, x, y):
    root_x = find(parents, x)
    root_y = find(parents, y)

    if ranks[root_x] > ranks[root_y]:
        parents[root_y] = root_x
    else:
        parents[root_x] = root_y
        if ranks[root_x] == ranks[root_y]:
            ranks[root_y] += 1

# 크루스칼 알고리즘 구현
def kruskal(graph):
    n = len(graph)
    edges = []
    
    # 모든 간선 추출 및 정렬
    for i in range(n):
        for j in range(i+1, n):
            if graph[i][j] != 0:
                edges.append((i, j, graph[i][j]))
    
    edges.sort(key=lambda x:x[2]) # 가중치 기준 오름차순 정렬
    
    mst_cost = 0 # MST의 전체 비용 저장 변수
    
    # Union-Find 자료구조 초기화
    parents = list(range(n))
    ranks = [0] * n
    
   # MST 생성 과정 (간선 선택)
   for edge in edges:
       u, v, cost = edge

       if find(parents, u) != find(parents, v): 
           union(parents, ranks, u, v)
           mst_cost += cost
   
   return mst_cost

# 사용 예시 
graph=[[0, 2, 0, 6, 0],
       [2, 0, 3, 8, 5],
       [0, 3, 0, 0, 7],
       [6, 8, 0, 9, 10],
       [0, 5, 7, 10, 11]]

min_spanning_tree_cost = kruskal(graph)
print(min_spanning_tree_cost)

• 위 코드에서 graph 리스트는 인접 배열 혹은 인접 리스트로 나타난 입력 그래프입니다. 함수 kruskal()은 주어진 그래프에 대해 크루스칼 알고리즘을 수행하며 MST의 전체 비용인 mst_cost 값을 반환합니다.
• 크루스칼 알고리즘은 각 단계마다 사이클 검사를 수행하기 위해 Union-Find 자료구조를 활용합니다. 이를 통해 사이클을 형성하지 않으면서 최소 스패닝 트리가 생성됩니다.

 

• 프림 알고리즘: 임의의 시작 정점부터 출발하여 신장트리 집합을 확장해 나가는 방식으로 최소 스패닝 트리를 만듭니다.

 

1. 임의의 시작 정점을 선택합니다.
2. 선택한 정점과 연결된 간선 중 가장 작은 가중치를 가진 간선을 선택합니다.
3. 선택한 간선으로 연결된 정점을 MST 집합에 추가합니다.
4. MST 집합에 포함되지 않은 정점들 중에서, MST와의 연결된 간선 중 가장 작은 가중치를 가진 간선을 선택합니다.
5. 3-4 단계를 모든 정점이 MST에 포함될 때까지 반복합니다.

import heapq

# 프림 알고리즘 구현
def prim(graph):
    n = len(graph)
    mst_cost = 0 # MST의 전체 비용 저장 변수
    
    visited = [False] * n # 방문 여부 확인을 위한 리스트
    min_heap = [] # 우선순위 큐로 사용할 최소 힙
    start_vertex = 0 # 임의로 시작 정점 설정
    
    visited[start_vertex] = True # 시작 정점 방문 처리

    for edge in graph[start_vertex]:
        heapq.heappush(min_heap, edge) # 시작 정점과 연결된 간선들 우선순위 큐에 삽입

    while min_heap:
        weight, v1, v2 = heapq.heappop(min_heap) # 최소 가중치 간선 추출
        
        if not visited[v2]: 
            visited[v2] = True 
            mst_cost += weight
            
            for edge in graph[v2]:
                if not visited[edge[2]]:
                    heapq.heappush(min_heap, edge) 

    return mst_cost

# 사용 예시 
graph=[[(2, 1), (3, 4)],
       [(1, 1), (3, 2), (4, 3)],
       [(0, 4), (1, 2)],
       [(0, 1), (1, 3), (4, 5)],
       [(3, 5), (1, 3)]]

min_spanning_tree_cost = prim(graph)
print(min_spanning_tree_cost)

• 위 코드에서 graph 리스트는 인접 리스트로 나타난 입력 그래프입니다. 함수 prim()은 주어진 그래프에 대해 프림 알고리즘을 수행하며 MST의 전체 비용인 mst_cost 값을 반환합니다.
• 프림 알고리즘에서는 우선순위 큐(Heap) 자료구조를 사용하여 현재 MST와 연결되지 않은 간선 중 최소 가중치인 것을 선택하게 됩니다. 이렇게 선택된 간선과 해당하는 정점들이 저번 단계에서 만든 MST 집합에 추가되어 새로운 후보가 됩니다.

 

코딩 테스트에서의 MST 접근 방법

 

• 일반적으로 코딩 테스트에서 최소 스패닝 트리 문제를 접할 때에는 다음과 같은 단계로 접근합니다.

 

1. 입력 분석: 주어진 입력 형식과 제약 조건을 분석하고, 필요한 자료구조와 변수를 초기화합니다.
2. 그래프 생성: 입력 정보를 바탕으로 그래프(간선 리스트 또는 인접 리스트 등)를 생성합니다.
3. 크루스칼 또는 프림 알고리즘 적용: 선택한 알고리즘을 사용하여 최소 스패닝 트리를 구합니다.
4. 결과 출력: 구한 최소 스패닝 트리의 가중치 합 또는 해당 간선들을 출력합니다.

 

1197번: 최소 스패닝 트리

 

  문제  

 

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

 

  해결 방법  

 

• 이 문제는 주어진 그래프에서 모든 정점을 연결하는 간선들 중 가중치의 합이 최소가 되는 트리를 찾는 문제입니다. 이러한 상황에서 크루스칼 알고리즘이나 프림 알고리즘과 같은 MST를 구하는 알고리즘이 활용됩니다.
• 여기서는 프림 알고리즘으로 접근해보겠습니다.

import heapq
import sys; input=sys.stdin.readline

def prim(start, edges):
    mst = []
    visited = [False] * V
    queue = []
    
    heapq.heappush(queue, (0, start))

    while queue:
        weight, node_idx = heapq.heappop(queue)

        if visited[node_idx]:
            continue
            
        visited[node_idx] = True
        mst.append(weight)

        for edge in edges[node_idx]:
            v2, cost_v2= edge
            
            if not visited[v2]:
                heapq.heappush(queue, (cost_v2, v2))

    return sum(mst)

V, E = map(int, input().split())
edges = [[] for _ in range(V)]

for _ in range(E):
   a, b, c = map(int, input().split())
   a -= 1
   b -= 1 
   
   edges[a].append((b, c))
   edges[b].append((a, c))

print(prim(0, edges))

 

• 위 코드에서 prim 함수는 주어진 그래프에 대해 프림 알고리즘을 수행하며 MST의 전체 비용 값을 반환합니다.
• 우선순위 큐(Heap) 자료구조를 사용하여 현재 MST와 연결되지 않은 간선 중 최소 가중치인 것을 선택하게 됩니다. 이렇게 선택된 간선과 해당하는 정점들이 저번 단계에서 만든 MST 집합에 추가되어 새로운 후보가 됩니다.

 
 

16398번: 행성 연결

 

  문제  

 

• 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다.
• 두 행성 간에 플로우를 설치하면 제국의 함선과 무역선들은 한 행성에서 다른 행성으로 무시할 수 있을 만큼 짧은 시간만에 이동할 수 있다. 하지만, 치안을 유지하기 위해서 플로우 내에 제국군을 주둔시켜야 한다.
• 모든 행성 간에 플로우를 설치하고 플로우 내에 제국군을 주둔하면, 제국의 제정이 악화되기 때문에 황제 윤석이는 제국의 모든 행성을 연결하면서 플로우 관리 비용을 최소한으로 하려 한다.
• N개의 행성은 정수 1,…,N으로 표시하고, 행성 i와 행성 j사이의 플로우 관리비용은 Cij이며, i = j인 경우 항상 0이다.
• 제국의 참모인 당신은 제국의 황제 윤석이를 도와 제국 내 모든 행성을 연결하고, 그 유지비용을 최소화하자. 이때 플로우의 설치비용은 무시하기로 한다.

 

  해결 방법  

 

• 이 문제는 N개의 행성을 모두 연결하는데 필요한 최소 비용을 구하는 문제입니다. 각 행성 간에는 비용이 주어져 있고, 이 비용은 양방향입니다. 이러한 상황에서 모든 행성을 연결하는 최소 비용을 구하려면 MST를 구해야 합니다.
• 크루스칼 알고리즘으로 접근할 수 있습니다. 먼저 입력된 그래프 정보를 가지고 간선 리스트를 생성하며, 가중치 순으로 정렬합니다. 그 후 Union-Find 자료구조를 사용하여 사이클 없이 간선들을 선택합니다.

import sys; input=sys.stdin.readline

def find(parents, x):
    if parents[x] != x:
        parents[x] = find(parents, parents[x])
    return parents[x]

def union(parents, ranks, x, y):
    root_x = find(parents, x)
    root_y = find(parents, y)

    if ranks[root_x] > ranks[root_y]:
        parents[root_y] = root_x
    else:
        parents[root_x] = root_y
        if ranks[root_x] == ranks[root_y]:
            ranks[root_y] += 1
            
N = int(input())
edges = []
parents = [i for i in range(N+1)]
ranks = [0] * (N+1)

for i in range(N):
    temp = list(map(int, input().split()))
    
    for j in range(i+1, N):
        edges.append((temp[j], i, j))

edges.sort()
total_cost = 0

for edge in edges:
    cost, a, b = edge
    
    if find(parents, a) != find(parents, b): 
        union(parents, ranks, a, b)
        total_cost += cost
        
print(total_cost)

 

• MST와 관련해서 심화적인 몇 가지 주제들도 있습니다.
• Boruvka's Algorithm: 최소 스패닝 트리를 구하는 다른 알고리즘으로, 복잡도가 O(ElogV)로 동작하며 여러 개로 분산된 서브그래프 상태에서도 활용할 수 있습니다.
• Reverse Delete Algorithm: 크루스칼 알고리즘과 유사하지만 역방향으로 진행하여 간선을 삭제하는 방식입니다. 간선의 가중치를 큰 순서대로 정렬하고, 가중치가 큰 간선부터 제거하면서 그래프의 연결성을 유지합니다.
• Minimum Spanning Tree Verification: 주어진 그래프가 최소 스패닝 트리인지 확인하는 방법에 대해 공부해볼 수 있습니다. 사이클 검사 등을 활용하여 정당성을 검증할 수 있습니다.
• 위 소개된 심화 주제들은 최소 스패닝 트리에 대한 더 깊은 이해와 응용력을 기르는 데 도움이 될 것입니다!