ABC 328 E번 복기 cost를 modulo로 나눈 최소 스패닝 트리 구하는법

1. 문제

 

E - Modulo MST (atcoder.jp)

E - Modulo MST

 

2. 풀이

 

단순하게 최소 스패닝 트리를 바로 찾으면, cost 자체는 최소일지 몰라도 그것을 modulo로 나눈 값이 최소라는 보장은 없다

 

다행히 정점 N <= 8이고 최대 간선의 수는 M <= 28이고 스패닝 트리가 될려면 N-1개의 간선을 선택해야하므로,

 

가능한 스패닝 트리의 집합은 최대 28C7 = 1184040가지이다.

 

따라서, 간선의 집합에서 n-1개를 선택하는 부분집합을 모두 구하고, 

 

해당 부분집합을 모두 순회해서 최소 스패닝 트리를 이루는 cost를 modulo로 나눈 값의 최솟값을 찾는다

 

크루스칼 알고리즘을 이용하면 간단하게 찾을 수 있는데,

 

특히 중요한 부분은 n-1개의 간선을 선택하는 부분집합에서 크루스칼 알고리즘을 수행할때, 순회하는 간선이 n-1개라고 하더라도,

 

union-find에 의해 n-1개를 선택한다는 보장이 없다.

 

그러니까 최초 m개의 간선 집합에서 n-1개의 간선을 선택하는 부분집합이 반드시 스패닝 트리라는 보장이 없으므로,

 

마지막에 count == n-1인지 검사하고, 그렇다면 최솟값을 갱신해줘야한다

 

from itertools import combinations

def find_parent(x,parent):
    
    if x != parent[x]:
        
        parent[x] = find_parent(parent[x],parent)
    
    return parent[x]

def union(a,b):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)

    if parent[a] < parent[b]:
        
        parent[a] = parent[b]
    
    else:
        
        parent[b] = parent[a]      

n,m,k = map(int,input().split())

edges = []

for _ in range(m):
    
    u,v,w = map(int,input().split())
    edges.append((w,u,v))

#스패닝 트리는 n-1개의 간선을 가지므로,
#간선 중 n-1개를 선택한 부분집합을 모두 찾는다
combs = combinations(edges,n-1)

answer = 10**18+1

for edge in combs:
    
    cost = 0
    count = 0

    parent = [i for i in range(n+1)]

    for w,u,v in edge:
        
        if find_parent(u,parent) != find_parent(v,parent):
            
            union(u,v)
            cost += (w)
            cost %= k
            count += 1
    
    #순회하는 간선이 n-1개더라도, 반드시 n-1개를 모두 택한다는 보장이 없다
    #부분집합이 스패닝 트리라는 보장이 없기 때문에, n-1개를 선택했는지 반드시 검사해줘야
    if count == n-1:
        
        if answer > cost:
            
            answer = cost

print(answer)