[백준 / 1922] 네트워크 연결 - Python

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

<풀이>

입력 받은 연결들을 작은 비용 순으로 정렬하고, 추가해가면 된다.

a와 b가 같은 입력이 있으므로 해당 경우는 무시한다.

 

<전체 코드>

import sys

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

connections = []
for _ in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    if a == b:
        continue
    connections.append([c, a, b])

connections.sort()
visit = []
cost = 0
for connection in connections:
    c, a, b = connection

    a_idx = -1
    b_idx = -1
    for i in range(len(visit)):
        if a in visit[i]:
            a_idx = i
        if b in visit[i]:
            b_idx = i
    if a_idx == -1 and b_idx == -1:
        visit.append([a, b])
        cost += c
    elif a_idx == -1:
        visit[b_idx].append(a)
        cost += c
    elif b_idx == -1:
        visit[a_idx].append(b)
        cost += c
    elif a_idx == b_idx:
        continue
    else:
        visit[a_idx].extend(visit[b_idx])
        visit.pop(b_idx)
        cost += c
    visit[0].sort()

    if len(set(visit[0])) == N:
        print(cost)
        break