[완전탐색-Union Find] 전력망 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

Union Find를 이용해 disjoint set을 찾아 노드의 수에 따른 차가 가장 큰 경우를 찾으면 되는 문제.

 

특별히 자체 구현 코드에서 마지막에 최종적으로 parents를 업데이트 하는 코드를 잊지 말자

def Find(v,parents) : 
    if parents[v] != v : 
        parents[v] = Find(parents[v],parents)
    return parents[v]

def Union(x,y,parents,rank) : 
    if rank[x]>rank[y] : 
        parents[y] = x
    if rank[x]<rank[y] : 
        parents[x] = y
    else : 
        parents[y] = x
        rank[x] += 1
    return parents, rank

def solution(n, wires):
    final_diff = []
    for i in range(len(wires)) : 
        wire_rest = wires[:i]+wires[i+1:]
    
        ## makeset
        parents = {}
        rank = {}
        for v in range(1,n+1) : 
            parents[v] = v
            rank[v] = 0
        
        for v1,v2 in wire_rest : 
            x = Find(v1,parents)
            y = Find(v2,parents)
            if x != y : 
                parents, rank = Union(x,y,parents,rank)
        
        ### 이 과정 잊지 말기
        for v in range(1,n+1) : 
            parents[v] = Find(v,parents) 
        
        cases = []
        for case in list(set(parents.values())) :
            cnt = 0
            for node in range(1,n+1) : 
                if parents[node] == case : 
                    cnt += 1
            cases.append(cnt)
        
        final_diff.append(abs(cases[0]-cases[1]))

    #print(final_diff)
    return min(final_diff)