[ 위클리 챌린지 ] [ 9주차 ] 전력망을 둘로 나누기

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

코딩테스트 연습 - 9주차

---

풀이 과정

---

1. 전선들중 하나씩 빼보면서 분리된 전력망에 각각 몇개의 송전탑이 들어가는지 확인
   • 각각의 송전탑이 어느 전력망에 속하는지 구하기 위해 Union-Find 알고리즘 사용
2. 트리의 특성 상, 하나의 노드라도 연결을 끊으면 두개의 그룹으로 나뉘어질거라 생각하여, 파이썬의 defaultdict를 활용하여 각 전력망에 있는 송전탑의 개수를 저장한 다음, 두 값의 차이의 절댓값과 기존 정답의 비교를 통해 정답을 갱신한다.

---

소스 코드

---

 

from collections import defaultdict

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    pa = find(parent, a)
    pb = find(parent, b)
    if pa != pb:
        parent[pa] = parent[pb]

def solution(n, wires):
    answer = int(10e9)
    for skip in range(len(wires)):
        parent = [i for i in range(n+1)]
        for idx, wire in enumerate(wires):
            if skip == idx:
                continue
            if find(parent, wire[0]) != find(parent, wire[1]):
                union(parent, wire[0], wire[1])
        
        group_value = defaultdict(int)
        for i in range(1, n+1):
            group_value[find(parent, i)] += 1
        values = list(group_value.values())
        groupA, groupB = values[0], values[1]
        answer = min(answer, abs(groupA - groupB))
             
    return answer