[프림] 5249 최소 신장 트리

0번부터 V번까지의 노드가 있고 E개의 간선이 주어지는 그래프가 있을 때 최소신장트리를 구성하는 가중치의 합을 출력한다.

---

프림 알고리즘

 

- 특정 정점을 시작으로 점진적으로 최소신장트리를 완성해나간다.

- 지금까지 선택한 정점을 검색하여 아직 선택하지않은 정점 중에 가중치가 가장 적은 정점을 선택한다.

 

구현

- 정점의 개수(V)와 간선의 개수(E)를 입력받는다.

- 간선의 개수만큼 노드a, 노드b, 가중치w를 입력받아 2차원 리스트로 그래프를 표현한다.

    V, E = map(int, input().split())

    graph = [[0 for _ in range(V+1)] for _ in range(V+1)]
    for _ in range(E):
        a, b, w = map(int, input().split())

        graph[a][b] = graph[b][a] = w

 

- 최소신장트리를 구성할 때 모든 정점은 한 번씩만 방문해야하기 때문에 방문표시를 위한 visited 리스트를 생성한다.

- 이미 방문한 노드 중 인접한 노드에서 가장 적은 가중치의 노드를 선택하기 위해 distance의 데이터로 최솟값을 찾는다.

- 출발할 노드를 0번으로 지정하였는데 최소신장트리는 싸이클이 없는 구조이기 때문에 임의의 노드로 시작해도 상관없다.

- 연결된 간선의 개수(connected_edge)가 V-1개가 될 때까지 정점들을 연결해 나간다.

    INF = 987654321
    visited = [False] * (V+1)
    distance = [INF] * (V+1)

    cur_node = 0
    visited[cur_node] = True
    distance[cur_node] = 0

    connected_edge = 0

 

- 처음 for문은 바로 이전에 선택했던 정점과 연결된 정점을 선택한다.

- 이를 통해 아직 방문하지않은 정점 중들의 최솟값을 갱신하는데

- 지금까지 선택한 정점과 인접한 정점들의 최솟값이 distance에 들어있다.

- 두 번째 for문은 distance를 통해 지금까지 방문한 노드에서 인접한 노드 중 최솟값을 갖는 노드를 선택하게된다.

    while connected_edge < V:

        for next_node in range(V+1):
            if not visited[next_node] and graph[cur_node][next_node] \
                and graph[cur_node][next_node] < distance[next_node]:
                distance[next_node] = graph[cur_node][next_node]

        min_dist = INF
        for next_node in range(V+1):
            if not visited[next_node] and distance[next_node] < min_dist:
                min_dist = distance[next_node]
                cur_node = next_node

        visited[cur_node] = True
        connected_edge += 1

---

전체 코드

import sys
sys.stdin = open("input.txt")

test_case = int(input())
for tc in range(test_case):
    V, E = map(int, input().split())

    graph = [[0 for _ in range(V+1)] for _ in range(V+1)]
    for _ in range(E):
        a, b, w = map(int, input().split())

        graph[a][b] = graph[b][a] = w

    INF = 987654321
    visited = [False] * (V+1)
    distance = [INF] * (V+1)

    cur_node = 0
    visited[cur_node] = True
    distance[cur_node] = 0

    connected_edge = 0
    while connected_edge < V:

        for next_node in range(V+1):
            if not visited[next_node] and graph[cur_node][next_node] \
                and graph[cur_node][next_node] < distance[next_node]:
                distance[next_node] = graph[cur_node][next_node]

        min_dist = INF
        for next_node in range(V+1):
            if not visited[next_node] and distance[next_node] < min_dist:
                min_dist = distance[next_node]
                cur_node = next_node

        visited[cur_node] = True
        connected_edge += 1

    answer = sum(distance)
    print("#{} {}".format(tc+1, answer))