[BOJ] 백준 16202번 MST 게임 | python 파이썬 코드, 해설, 풀이

백준 16202번 MST 게임 문제 파이썬 풀이입니다.

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

16202번: MST 게임

문제 이름에서 대놓고 알고리즘을 알려주고 있기 때문에 MST를 푸는 방법인 Kruskal 알고리즘으로 풀 수 있었습니다.

Edge의 최대가 10000개여서 O(ElogE)인 알고리즘으로 K번 돌아도 충분한 문제였습니다.

 

주요코드

line 10 ~ 22 : 유니온파인드 함수 line 34 : 입력 받은 edge를 가중치로 sort 해주는 부분(사실 가중치 순서로 입력 받으니 굳이 정렬할 필요는 없음) line 40 ~ 44 : 가중치 작은거부터 순회하면서 같은 부모 node인지 확인 후 다르면 union 작업을 해주면서 연결안된 node를 연결해줌, 이미 연결된거면 건너뜀(이미 가중치 낮은 edge에서 연결되었다는 뜻)

 

전체코드

import sys
import copy
from collections import deque
 
input = sys.stdin.readline
ans = 0
cnt = 0
 
 
def find(x):
    if (parent[x] != x):
        return find(parent[x])
    return x
 
 
def union(a, b):
    a = find(a)
    b = find(b)
    if (a < b):
        parent[b] = a
    else:
        parent[a] = b
 
 
n, m, k = map(int, input().split())
 
parent = [i for i in range(n + 1)]
 
edges = []
 
for i in range(m):
    a, b = map(int, input().split())
    edges.append([i + 1, a, b])
edges.sort()
 
for i in range(k):
    result = 0
    visited = []
    parent = [i for i in range(n + 1)]
    for edge in edges:
        cost, a, b = edge
        if (find(a) != find(b)):
            union(a, b)
            result += cost
            visited.append(edge)
 
    if (len(visited) == n - 1):
        print(result, end=" ")
    else:
        print(0, end=" ")
    edges = edges[1:]
print()