[프로그래머스] 9주차_전력망을 둘로 나누기

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

코딩테스트 연습 - 9주차

 

DFS 알고리즘으로 풀었고 리프 노드를 시작으로 하여 해당 노드의 전선 연결을 끊었을 때 남아 있는 송전탑의 개수(하위 노드의 개수 + 1)를 부모 노드의 result[] 에 더했다. (리프 노드는 result[] = 1)

 

만들어진 result[] 와 n - result[] 의 차이의 절대값과 result[0] 중 최솟값을 result[0] 으로 잡고 최종적으로 result[0] 을 반환한다. 

 

from collections import defaultdict

def solution(n, wires):
    answer = -1
    tree = defaultdict(list)
    visit = [1] + [0] * n
    result = [n] + [1] * n
    
    for wire1, wire2 in wires:
        tree[wire1].append(wire2)
        tree[wire2].append(wire1)
    
    rf(tree, 1, visit, result)
    answer = result[0]
    
    return answer
    
def rf(tree, i, visit, result):
    
    for wire in tree[i]:
        if visit[wire] == 0:
            visit[wire] = 1 
            rf(tree, wire, visit, result)
            result[i] += result[wire]

    result[0] = min(result[0], abs(len(result) - 1 - 2 * result[i]))
    
print(solution(9, [[1, 3], [2, 3], [3, 4], [4, 5], [4, 6], [4, 7], [7, 8], [7, 9]])) # 3