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

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

Question

Language: Python

트리로 된 전력망에서 전선을 하나 끊게 되면 2개의 트리형태의 전력망이 생성된다. 이때 각 전력망이 가지는 송전탑의 개수의 차이를 최소화하는 것이다. n이 2이상 100이하이므로 모든 경우에 대해서 송전탑 개수 차이를 비교해도 시간 내에 풀이가 가능하다.

우선, 같은 전력망에 있는지를 판별하기 위해 disjoint set을 활용한다.

Algorithm

for i in range(len(dungeons)):
    if not visited[i] and k>=dungeons[i][0]:
        visited[i]=True
        dfs(k-dungeons[i][1],visited,dungeons,[i])
        visited[i]=False

다음과 같이 모든 경우의 대해서, 방문 하거나, 방문 안 하거나의 경우를 따져서 재귀문을 통해 답을 구하면 된더.

Solution

from collections import Counter
from math import inf
def find_parent_compressed(parents,x):
    if x!= parents[x]:
        parents[x]=find_parent_compressed(parents,parents[x])
    return parents[x]
def union_parents(parents,x,y):
    pre_x=find_parent_compressed(parents,x)
    pre_y=find_parent_compressed(parents,y)
    
    if pre_x < pre_y:
        parents[pre_x]=pre_y
    else:
        parents[pre_y]=pre_x
        
def solution(n, wires):
    answer=inf
    for i in range(n-1):
        parents=[i for i in range(n+1)]

        for j in range(n-1):
            if i==j:
                continue
            
            union_parents(parents,wires[j][0],wires[j][1])

        #마지막에 한 번 더 부모 노드를 최신화해준다.
        for v in range(1,n+1):
            find_parent_compressed(parents,v)

        answer=min(answer,abs(list(Counter(parents[1:]).values())[0]-list(Counter(parents[1:]).values())[1]))
    return answer