Programmers[lv-2] 전력망을 둘로 나누기

from collections import Counter
INF = float('INF')

def solution(n, wires):
    def find(x, parent):
        if parent[x] != x:
            parent[x] = find(parent[x], parent)
        return parent[x]
    
    def union(a, b, parent):
        a = find(a, parent)
        b = find(b, parent)
        if a > b:
            parent[a] = b
        else:
            parent[b] = a
        return parent
        
    minimum = INF
    for i in range(n):
        parent = [i for i in range(n+1)]
        for j in range(n-1):
            if j == i:
                continue
            union(wires[j][0], wires[j][1], parent)
            
        temp = []
        for t in range(1, n+1):
            temp.append(find(t, parent))
            
        counter = Counter(temp)
        counter = list(counter.values())
        minimum = min(minimum, abs(counter[0] - counter[1]) if len(counter) != 1 else counter[0]) 
    return minimum
            

회고

• 풀이 방법은 보자마자 떠올려서 분리집합을 사용하기로 하였다.

• 다만 두가지 부분에서 애를 먹었는데 우선 집합을 합친 다음 한번 find로 재탐색 해주어야 제대로 된 부모노드를 저장할 수 있고 다음으로 나눈 결과가 한개인 경우 마지막 리스트에 값이 [9, 0] 즉 한 뭉텅이로 나누어진 경우 리스트의 길이가 1이므로 예외처리를 해주어야 한다.

• 문제를 풀며 새로 얻은 지식은 Counter를 사용해 조금 더 쉽게 리스트 또는 집합의 개수를 딕셔너리 형태로 받을 수 있었다는것이다.