[백준 / 1997] 최소 스패닝 트리 - Python

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

1197번: 최소 스패닝 트리

<풀이>

1. 가중치가 가장 작은 순서로 입력을 정렬한다.

2. 방문 리스트를 작성하되 연결되어 있지 않으면 다른 리스트로 작성한다.

ex) 이전에 1,2 노드를 방문했고, 다음에 2,3 노드를 방문하면 방문 리스트에 3을 추가한다. 만약 4,5 노드를 방문하면 새 리스트에 4,5를 입력한다. 만약 다음에 3,4 노드를 방문하면 두 리스트를 합쳐서 1,2,3,4,5 리스트로 만든다.

 

<전체 코드>

# Pypy3 제출

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

route = []
for _ in range(E):
    a, b, c = map(int, input().split())

    route.append([c, a, b])

route.sort()

visit = []
ans = 0

for dis, no1, no2 in route:

    idx1 = -1
    idx2 = -1

    for i in range(len(visit)):
        if no1 in visit[i]:
            idx1 = i
        if no2 in visit[i]:
            idx2 = i

    if idx1 == -1 and idx2 == -1:
        visit.append([no1, no2])
        ans += dis
    elif idx1 == idx2:
        continue
    elif idx1 == -1:
        visit[idx2].append(no1)
        ans += dis
    elif idx2 == -1:
        visit[idx1].append(no2)
        ans += dis
    else:
        visit[idx1].extend(visit[idx2])
        visit.pop(idx2)
        ans += dis

    if len(visit[0]) == V:
        break

print(ans)