[프로그래머스/파이썬] 전력망을 둘로 나누기

 

 

나의 풀이

def get_children(tree, index):
    global children
    children[index] = 1
    for child in tree[index]:
        if not children[child]:
            get_children(tree, child)
            children[index] += children[child]

def solution(n, wires):
    global children
    tree = [[] for _ in range(n)]
    children = [0] * n

    for wire in wires:
        a, b = wire
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    get_children(tree, 0)

    return abs(n - 2 * min(children, key=lambda x: abs(n//2 - x)))

 - 1(코드에선 0)을 root로 봤을때, 자손 노드의 개수 + 1 을 저장

 - n의 중간값에서 가장 가까운 값을 찾으면 그것이 나눴을 때 한쪽 전력망의 개수

 

 

부분집합을 활용한 풀이

def solution(n, wires):
    ans = n
    for sub in (wires[i+1:] + wires[:i] for i in range(len(wires))):
        s = set(sub[0])
        [s.update(v) for _ in sub for v in sub if set(v) & s]
        ans = min(ans, abs(2 * len(s) - n))
    return ans

 

 

 

union-find 알고리즘을 활용한 풀이

uf = []

def find(a):
    global uf
    if uf[a] < 0: return a
    uf[a] = find(uf[a])
    return uf[a]

def merge(a, b):
    global uf
    pa = find(a)
    pb = find(b)
    if pa == pb: return
    uf[pa] += uf[pb]
    uf[pb] = pa

def solution(n, wires):
    global uf
    answer = int(1e9)
    k = len(wires)
    for i in range(k):
        uf = [-1 for _ in range(n+1)]
        tmp = [wires[x] for x in range(k) if x != i]
        for a, b in tmp: merge(a, b)
        v = [x for x in uf[1:] if x < 0]
        answer = min(answer, abs(v[0]-v[1]))

    return answer