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

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

프로그래머스

cnt_list = []

def dfs(graph, v, visited): 
    global cnt
    visited[v] = True  # 방문 처리
    for i in graph[v]:  # v번 노드와 연결된 노드들
        if not visited[i]:  # 방문하지 않았으면
            cnt+=1
            dfs(graph,i,visited)

def solution(n, wires):
    global cnt,cnt_list
    cnt_list=[]
    answer=n
    graph=[[] for i in range(n+1)]
    
    for a, b in wires: # 양방향 그래프 생성
        graph[a].append(b)
        graph[b].append(a) 
    
    for a, b in wires: # 각 간선을 하나씩 끊어보면서 연결 요소 크기 차이 계산
        graph[a].remove(b) # 간선 제거
        graph[b].remove(a)        
        visited=[False]*(n+1) # 방문 여부 초기화
        cnt=1  # 시작 노드 포함
        dfs(graph,1,visited)  # 1번 노드에서 DFS 시작
        part1=cnt  # 첫 번째 연결 요소 크기
        part2=n-cnt  # 두 번째 연결 요소 크기 
        answer=min(answer, abs(part1 - part2)) # 두 연결 요소 간의 차이의 최소값
        
        graph[a].append(b) # 제거한 간선 복구
        graph[b].append(a)
    
    return answer