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

def solution(n, wires):
    graph = [[] for _ in range(n + 1)]
    for u, v in wires:
        graph[u].append(v)
        graph[v].append(u)

    def dfs(node, parent):
        cnt = 1  # 방문한 노드 카운트(송전탑의 개수)
        for child in graph[node]:
            if child != parent:
                cnt += dfs(child, node)
        return cnt

    min_diff = float("inf")  # 송전탑의 최소 차이 개수
    for u, v in wires:
        # 간선 제거
        graph[u].remove(v)
        graph[v].remove(u)

        diff = abs((n - dfs(u, v)) - dfs(u, v))  # 나머지 송전탑의 개수 - 탐색한 송전탑의 개수
        min_diff = min(min_diff, diff)  # 최소 차이 개수 갱신

        # 간선 복원
        graph[u].append(v)
        graph[v].append(u)
    return min_diff