[SW Expert Academy]5249번 최소 신장 트리

그래프에서 사이클을 제거하고 모든 노드를 포함하는 트리를 구성할 때, 가중치의 합이 최소가 되도록 만든 경우를 최소신장트리라고 한다.

0번부터 V번까지의 노드와 E개의 간선을 가진 그래프 정보가 주어질 때, 이 그래프로부터 최소신장트리를 구성하는 간선의 가중치를 모두 더해 출력하는 프로그램을 만드시오.


[입력]

첫 줄에 테스트 케이스의 개수 T가 주어지고, 테스트 케이스 별로 첫 줄에 마지막 노드번호 V와 간선의 개수 E가 주어진다.

다음 줄부터 E개의 줄에 걸쳐 간선의 양 끝 노드 n1, n2, 가중치 w가 차례로 주어진다. 

1<=T<=50, 1<=V<=1000, 1<=w<=10, 1<=E<=1000000

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

 

주의 사항)

0번부터 V번까지니까 V+1개이다.

 

TC = int(input())
for tc in range(1, TC+1):
    V, E = map(int, input().split())
    adj = [[0]*(V+1) for _ in range(V+1)]
    for i in range(E):
        # 시작 끝 가중치
        s, e, c = map(int, input().split())
        adj[s][e] = c
        adj[e][s] = c # 무방향이니 반대도 넣는다

    # key, p , mst 준비
    INF = float('inf') # 아주 큰값을 세팅. 변수에 담나놈
    key = [INF] * (V+1)
    # print(key)
    p = [-1] * (V+1)
    mst = [False] * (V+1)

    # 시작점은 그냥 0번으로 함
    key[0] = 0
    cnt = 0
    result = 0

    # key가 최소이고 아직 mst가 아닌 정점 선택해서 U라고 이름 붙이고 mst로 포함시킨다.
    # 그리고 key 삾을 갱신
    while cnt < V+1 :
        min = INF
        u = -1
        for i in range(V+1):
            if not mst[i] and key[i] < min:
                min = key[i]
                u = i
        mst[u] = True
        result += min
        cnt += 1
        # u에 인접하고, 아직 mst가 아니고, w에서 'key[w] > u-w' 가중치면 갱신
        for w in range(V+1):
            if adj[u][w] > 0 and not mst[w] and key[w] > adj[u][w]:
                key[w] = adj[u][w]
                # 부모도 갱신
                p[w] = u

    print(f'#{tc} {result}')