[Union-Find][BFS] 전력망을 둘로 나누기

전력망을 둘로 나누기

프로그래머스

 

• 내 풀이- union find
  • 완탐이라서 한번씩 다 잘라가면서 차이 계산
  • union-find로 연결된 탑 수 구할때 주의해야할 점
    • 일반적인 union-find로 하면 wires 입력값이 순서대로 된 경우가 아니면
    • 앞에서 묶여있던 그룹의 다른 값들이 뒤에 더 작은 값이 나와도 업데이트 되지 않는 경우가 생김
    • 새로운 값마다 확인해서 업데이트 해줄때 앞에 애들을 전부 다시 update

#update 해주는 코드
def update_component(root, old_root, new_root):
    for i in range(len(root)):
        if root[i] == old_root:
            root[i] = new_root

from collections import deque, Counter

def solution(n, wires):
    answer = int(1e9)
    root=[i for i in range(n+1)]

    def union(root, x,y):
        rx=find(root, x)
        ry=find(root, y)
        if rx < ry:
            update_component(root, ry, rx)
        elif ry < rx:
            update_component(root, rx, ry)
    
    def find(root, x):
        if root[x]!=x:
            root[x]=find(root, root[x])
        return root[x]
    
    def update_component(root, old_root, new_root):
        for i in range(len(root)):
            if root[i] == old_root:
                root[i] = new_root
    
    for idx,wire in enumerate(wires):
        tmp=root[:]
        x,y=wire
        for idx2, wire2 in enumerate(wires):
            if idx==idx2: continue
            a,b=wire2
            union(tmp, a,b)
        
        cnt=list(Counter(tmp[1:]).values())
        answer=min(answer, abs(cnt[1]-cnt[0]))
        
    return answer