[proj] 전력망을 둘로 나누기

모든 간선을 자르고 갯수 구하고 최소값 갱신하는 방향

dfs로 하위로 내려가면서 자식의 갯수를 구함
해당 노드의 연결된 노드를 구하되 다시 상위로 올라가면 안되기 때문에 부모 노드가 무엇인지 계속 알려줘야함 부모노드 뿐만 아니라 자른 간선 상의 짝 노드도 접근하면 안됨(최초로 dfs 시작할 때 부모 취급해버리면 됨)

반례

tests = [


   [9, [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]],
    [4, 	[[1,2],[2,3],[3,4]]],
    [7, [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]]
] 

for test in tests:
    n, arr = test
    print(solution(n, arr))
    
// answer: 3 0 1

코드

def solution(n, wires):
    ## 각 관계를 끊고 하위 갯수 몇개인지 판별 해보기
    graph = [[] for _ in range(n+1)]
    answer = float("inf")
    
    def dfs(node, parent):
        count =1
        for child in graph[node]:
            if child !=parent:
                count +=dfs(child, node)

        return count
    
    ## 그래프 관계 입력 받기
    for wire in wires:
        a,b = wire
        graph[a].append(b)
        graph[b].append(a)
        
    ## 그래프 관계 한개씩 끊어보기
    for wire in wires:
        a,b = wire
        ## 끊어보기
        graph[a].remove(b)
        graph[b].remove(a)
        
        ## 하위 연결된거 갯수 세기
        count_a = dfs(a,b)
        count_b = n - count_a
        
        answer = min(answer, abs(count_a-count_b))
        
        ## 다시 연결하기
        graph[a].append(b)
        graph[b].append(a)

    return answer