전력망을 둘로 나누기

프로그래머스

 

유형에는 완전탐색이라고 되어 있기하던데 난 다른 방식으로 풀었다.

n개의 송전탑이 하나의 트리 형태로 연결되어 있고, 그 중 하나의 전선을 끊어 두 개의 트리로 만든다.

그리고 각 트리에서의 원소 개수 차이가 최소가 되는 그 최소값을 구하면 된다.

 

union-find를 통해서 풀었다.

반복문을 통해 각 전선을 하나씩 제거하면서 union-find연산을 통해 각 송전탑들이 속하고 있는 트리를 저장한다.

그리고 각 경우에 대해, 트리에 속한 송전탑의 개수 차이가 최솟값인 경우를 갱신해서 리턴한다.

 

---

풀이 코드

from collections import Counter

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        


def solution(n, wires):
    answer = 1000000 # 송전탑의 개수 차이의 최솟값
    
    parent = [i for i in range(n+1)]
    
    
    for i in range(len(wires)):
        for j in range(len(wires)):
            # i번째에 해당하는 전선은 제외하고 union한다.
            if i == j:
                continue

            a = wires[j][0]
            b = wires[j][1]
            
            union_parent(parent, a, b)
        
        # temp = i번 송전탑의 부모 송전탑들을 저장하는 리스트
        temp = []
        for i in range(1, n+1):
            temp.append(find_parent(parent, i))

        # temp_count = 각 송전탑이 속한 부모 송전탑들의 개수를 저장하고 있는 리스트
        temp_count = Counter(temp).most_common(2)
        
        # 두 송전탑 개수 차이를 최솟값으로 갱신
        if abs(temp_count[0][1] - temp_count[1][1]) < answer:
            answer = abs(temp_count[0][1] - temp_count[1][1])

        # parent 리스트 다시 초기값으로 초기화
        parent = [x for x in range(n+1)]
        
    return answer

 

 

 

여기서 주의해야할 점은 

        # temp = i번 송전탑의 부모 송전탑들을 저장하는 리스트
        temp = []
        for i in range(1, n+1):
            temp.append(find_parent(parent, i))

이 부분이다.

 

union_parent를 통해 parent를 합쳐준 후에, 다시 parent의 각 원소에 find_parent를 통해 루트 parent를 찾아서 새로운 리스트에 넣어줘야 한다.

왜냐하면 union_parent를 통해 갱신된 parent리스트의 각 원소의 값에 무조건 루트 parent가 들어가 있다고 보장할 수 없기 때문이다.