[BOJ] 1197번 최소 스패닝 트리 / 사용언어 : 파이썬(python)

※ 문제링크

1197번: 최소 스패닝 트리

※ 관련개념

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

해당 문제는 최소 스패닝 트리에 대한 개념을 이해할 수 있는 문제로, 2가지 방법으로 해결이 가능했다. 최소 신장트리에 대한 내용 및 문제 해결을 위해 이해가 필요한 프림 알고리즘과 크루스칼 알고리즘에 대해 알기 위해 참조했던 사이트를 링크를 걸어두었으니 개념이해 필요하다면 참고하면 좋을 듯 하다. 사실 해당 문제는 앞서 언급한 최소신장트리와 두 가지 알고리즘 중 1가지만 알면 별다른 응용없이 풀 수 있는 문제였기에 개념을 이해 후 구현하는데는 어려움이 없었다. 자세한 문제풀이방법과 코드는 아래와 같다. (프림알고리즘과 크루스칼 중 어떤 것을 쓰느냐에 따라 입력값을 다르게 구현)

1. 입력받은 값들을 변수와 리스트를 활용하여 저장해준다.(프림은 그래프형태로, 크루스칼은 간선형태로 저장)

2. 파이썬에 내장된 힙을 활용하여 정렬하고, 각각의 알고리즘 함수를 활용하여 최소 스패닝 트리를 구현하면서 가중치를 기록한다.

3. 함수 종류 후 결과값을 출력한다.(시간 및 메모리 절감을 위해 sys를 사용하였습니다.)

 

# Prim 형태로 해결시도 - 해결
from heapq import heappush, heappop
import sys

V, E = map(int, input().split()) # V: 정점의 개수 / E: 간선의 개수
graph = [[] for _ in range(V+1)]
for _ in range(E):
    cp1, cp2, wei = map(int, input().split())
    graph[cp1].append([wei, cp2])
    graph[cp2].append([wei, cp1])

def MST_Prim(start, graph, V):
    heap = []
    visited = [False for _ in range(V+1)]
    visited[start] = True
    for line in graph[start]:
        heappush(heap, line)

    ans = 0
    cnt = 1
    while heap:
        if cnt == V:
            print(ans)
            return 
        wei, cp = heappop(heap)
        if visited[cp]:
            continue
        else:
            cnt += 1
            visited[cp] = True
            ans += wei
            for line in graph[cp]:
                heappush(heap, line)

MST_Prim(1, graph, V)

# Kruskal 형태로 해결시도 - 해결
from heapq import heappush, heappop
import sys

# input = sys.stdin.readline
V, E = map(int, input().split()) # V: 정점의 개수 / E: 간선의 개수
heap = []
for _ in range(E):
    cp1, cp2, wei = map(int, input().split())
    heappush(heap, [wei, cp1, cp2])

root = [i for i in range(V+1)] # 각 정점별 노드 기록용도

def union(node1, node2):
    node1 = find(node1)
    node2 = find(node2)

    if node1 < node2:
        root[node2] = node1
    else:
        root[node1] = node2

def find(node):
    if node == root[node]: # 루트노드가 자기자신인 경우
        return node
    root[node] = find(root[node]) # 루트노드가 자기자신이 아닌 경우
    # 자기자신을 루트노드로 가지는 노드를 찾아서 반환
    return root[node]

def MST_kruskal():
    ans = 0
    while heap:
        wei, node1, node2 = heappop(heap)
        if find(node1) != find(node2):
            union(node1, node2)
            ans += wei
    print(ans)
    return 

MST_kruskal()

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.