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

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

bfs로 모든 노드를 끊어보고 그 중에서 네트워크 2개의 송전탑 개수의 차이가 최소가 되는 값을 return 한다

from collections import deque
               
def bfs(n,target, graph):
    cnt = 1
    q = deque()
    q.append(1)
    visited = [0]*(n+1)
    visited[1] = 1
    while q:
        node = q.popleft()
        for i in graph[node]:
            if not visited[i] and i!=target:
                cnt+=1
                q.append(i)
                visited[i] = 1
                
    return cnt
        
def solution(n, wires):
    answer = 1e9
    graph = [[] for _ in range(n+1)]
    for x,y in wires:
        graph[x].append(y)
        graph[y].append(x)
    
    for i in range(1,n+1):
        cnt = bfs(n,i,graph)
        answer = min(answer, abs(n-2*cnt))
            
    return answer