백준 문제 풀이 - 최소 스패닝 트리 1197번

📜 문제 이해하기

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

💡 문제 재정의

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

✏️ 계획 수립

prim의 알고리즘으로 문제를 해결하면 된다. 단 이 때 간선의 개수 E가 정점의 개수 V보다 10배 더 크기때문에 sparse graph가 아닌 dense graph로 볼 수 있다. 따라서 priority queue를 구성할때는 heap이 아니라 unsorted sequence로 구성해야 제한시간안에 들어올 수 있다.

💻 계획 수행

import sys
from collections import deque

if __name__ == '__main__':
    INF = 2147483648
    V, E = map(int, sys.stdin.readline().split())

    node_status = ['U' for _ in range(V + 1)]
    node_distance = [INF for _ in range(V + 1)]
    adj = [[] for _ in range(V + 1)]

    # 안쓰는 값 초기화
    node_status[0] = 'N'
    node_distance[0] = 0

    # 인접 리스트 받기
    for i in range(E):
        v1, v2, d = map(int, sys.stdin.readline().split())
        adj[v1].append((v2, d))
        adj[v2].append((v1, d))

    node_status[1] = 'T'
    node_distance[1] = 0
    for adj_node in adj[1]:
        node_status[adj_node[0]] = 'F'
        node_distance[adj_node[0]] = adj_node[1]

    while 'F' in node_status:
        next_index = 0
        min_distance = INF
        # 제일 짧은 가중치 찾기
        for i, d in enumerate(node_distance):
            if node_status[i] == 'F' and min_distance > d:
                next_index = i
                min_distance = d
        # 트리에 편입
        node_status[next_index] = 'T'

        # 편입된 노드와 인접한 노드 처리
        for adj_node in adj[next_index]:
            # replace U to F
            if node_status[adj_node[0]] == 'U':
                node_status[adj_node[0]] = 'F'
            # decrease key
            if adj_node[1] < node_distance[adj_node[0]] and node_status[adj_node[0]] == 'F':
                node_distance[adj_node[0]] = adj_node[1]

    print(sum(node_distance))

🤔 회고

이 프로그램의 시간복잡도를 살펴보자. 정점의 개수를 N, 간선의 개수를 M이라고 할 때 다음과 같다.
1) 처음 데이터를 초기화하는 부분 : O(N)
2) 인접 리스트를 입력받는 부분: O(M)
3) 첫번째 노드 초기화: O(dev(v))
3) while문이 도는 횟수: O(N)
3-1) 가중치를 찾는 for문 횟수: O(N)
3-2) 인접한 노드를 처리하는 횟수: O(dev(v))

위 내용에 따르면 프로그램은 N의 갯수에 지배적임을 알 수 있다. 따라서 이 프로그램의 시간복잡도는 O(N^2)이 된다.