LV 2: 전력망을 둘로 나누기

문제 링크

LV 2: 전력망을 둘로 나누기

구현 방식

• brute force + find-union을 이용해서 풀어주었다
• wires의 길이만큼 for문을 돌면서 현재 위치의 wire를 끊어준다면 송전탑이 트리 형태로 연결되어 있기 때문에, 두 개의 전력망으로 나뉘게 된다
  • 전력망을 끊어준 후, 매 반복마다 parent를 union해주고 diff 값(두 전력망이 가지고 있는 송전탑 개수의 차이)를 추가해주었다

코드

def solution(n, wires):
    N = len(wires)
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(a, b):
        a = find(a); b = find(b)
        if a < b: parent[b] = a
        else: parent[a] = b
            
    diff = []
    for i in range(N):
        parent = [_ for _ in range(n+1)]
        for j in range(N):
            if i == j: continue
            union(wires[j][0], wires[j][1])
        
        for j in range(1, n+1): find(j)
        
        parent_nodes = list(set(parent[1:]))
        diff.append(abs(parent.count(parent_nodes[0]) - parent.count(parent_nodes[1])))
        
    return min(diff)