[알고리즘] 탐욕법 - 프림 알고리즘 코드 (Greedy Approach - Prim's Algorithm Code)

문제)

Description

교재와 강의자료를 참고하여 Algorithm 4.1 프림 알고리즘의 구현을 완성하시오.

그래프의 입력은 간선의 집합으로 주어지며,

출력값은 그리디 알고리즘의 각 단계별로 nearest 배열의 변화를 출력하고,

F 집합에 추가되는 간선을 순서대로 출력한다.

Input

첫 줄에 정점의 개수 n, 간선의 개수 m이 주어진다.

두 번째 줄부터 다음과 같은 형태로 m 개의 간선이 주어진다.

u v w

u와 v는 정점의 번호이고, 1부터 n까지의 자연수로 표시한다.

w는 간선 <u, v>의 가중치이며, 양의 정수 값으로 주어진다.

Output

프림 알고리즘의 초기 단계부터 종료 단계까지(n-1 times)

nearest 배열의 값을 한 단계에 한 줄씩 출력한다.

첫번째 정점(v1)을 선택하는 전략이므로

nearest 배열의 값은 2번부터 n번까지만 출력한다. (i = 2 .. n)

이후로, 프림 알고리즘의 F 집합에 포함되는 간선을 순서대로 출력한다.

u v w

Sample Input 1

5 7
1 2 1
1 3 3
2 3 3
2 4 6
3 4 4
3 5 2
4 5 5

Sample Output 1

1 1 1 1
1 1 2 1
1 1 3 3
1 1 3 3
1 1 3 3
2 1 1
3 1 3
5 3 2
4 3 4

 

코드)

import sys
input = sys.stdin.readline

INF = 9999       # 경로가 없을 때


def func(F):
    for i in range(2, vertex_num + 1):
        nearest[i] = 1      # i와 가장 가까운 vertex는 1이라고 가정하고 시작
        distance[i] = W[1][i]       # 거리를 1과의 거리로 동기화 시킴

    print(*nearest[2:], sep=' ')

    for _ in range(vertex_num - 1):
        # edge가 vertex_num - 1개 추가되어야 하므로 범위를 이렇게 정함
        min = INF
        min_idx = -1
        for i in range(2, vertex_num + 1):      # 2부터 vertex_num까지 최소를 찾는 과정
            if 0 <= distance[i] < min:
                min = distance[i]
                min_idx = i

        F.append((min_idx, nearest[min_idx]))       # min_idx와 nearsest[min_idx]의 간선을 넣는다.
        distance[min_idx] = -1      # 추가했으므로 거리는 -1로 설정

        for i in range(2, vertex_num + 1):
            # 새로운 vertex를 집합에 추가했으므로, 새로운 vertex와 V-Y의 거리도 업데이트 해야함 (최소가 되게)
            if distance[i] > W[min_idx][i]:     # 만약 기존의 거리보다 새로운 vertex의 거리가 짧으면 업데이트 함
                distance[i] = W[min_idx][i]
                nearest[i] = min_idx

        print(*nearest[2:], sep=' ')


vertex_num, edge_num = map(int, input().split())        # 정점의 개수와 간선의 개수를 입력 받는다. 정점은 1부터 n까지의 자연수로 표시한다.

W = [[INF] * (vertex_num + 1) for _ in range(vertex_num + 1)]       # adjacency matrix, INF로 초기화하고 후에 값을 받을 예정
nearest = [1] * (vertex_num + 1)        # v_i에 가장 가까운 Y에 속한 정점의 인덱스, 1부터 시작하므로 1로 초기화
distance = [-1] * (vertex_num + 1)     # v_i와 nearest[i] 사이의 거리

for _ in range(edge_num):
    # 가중치를 입력 받음
    i, j, weight = map(int, input().split())
    W[i][j] = weight
    W[j][i] = weight

for i in range(1, vertex_num):
    # 본인과의 거리는 0
    W[i][i] = 0

F = list()      # 간선의 집합

func(F)

for i in range(vertex_num - 1):
    # 간선의 정보와 가중치를 출력함
    i, j = F[i]
    weight = W[i][j]
    print(i, j, weight)

 

 

제가 많이 피곤하나보네요,,

위에가 코드 결과고 아래가 output인데, 두 개가 같다고 보고 계속 뭐가 문제인지 찾기만 했네여 ,,,, 하, ,,,, ,,, ,