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

출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 전력망을 둘로 나누기

풀이

문제에서 트리형태이지만 어떤 노드가 루트인지 알려주지 않았다. 확인해보니 어떤 노드를 루트로 하던 간에 똑같은 결과가 나오는 것을 알 수 있었다.
1. 노드 1을 루트로 정하고 트리를 만든다.
2. 루트를 포함하여 트리의 노드 개수를 구하는 메서드를 만든다.
3. 각 노드에 만든 메서드를 적용해가면서 나누어진 두 트리의 차이가 가장 작을 때의 차이를 반환한다.

코드

def solution(n, wires):
    
    tree = {}
    # 루트가 1인 트리 만드는 메서드
    def make_tree(root):
        tree[root] = []
        for p, c in wires:
            if root == p and c not in tree:
                tree[root].append(c)
                make_tree(c)
            elif root == c and p not in tree:
                tree[root].append(p)
                make_tree(p)
    
    # 트리 만들기
    make_tree(1)

    # 루트를 포함한 트리의 노드 개수 구하는 메서드
    def count_child(root):
        res = 1
        for child in tree[root]:
            res += count_child(child)
        return res
    
    answer = 101
    for i in range(n):
        answer = min(answer, abs(n - 2 * count_child(i + 1)))
    
    return answer

다른 사람 풀이를 보며 알게 된 점

시간이 되면 다른 사람 풀이에서 교집합을 이용해 느리지만 엄청 간단하게 푼 풀이도 분석해야겠다.