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

스스로 푼 문제: O
걸린 시간: 10분

문제

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

풀이

각 와이어가 없는 상황(총 N개)에 대해서 bfs를 통해 한 쪽 전력망의 송전탑 개수를 파악한 뒤 두 송전탑 개수의 차에 대하여 min을 갱신한다.

코드

import collections

def solution(n, wires):
    # 트리
    graph = collections.defaultdict(list)
    for a, b in wires:
        graph[a].append(b)
        graph[b].append(a)
    
    answer = n
    for a, b in wires:
        # 와이어 제거
        graph[a].remove(b)
        graph[b].remove(a)
        
        # bfs로 연결된 송전탑 탐색
        visited = [0] * (n+1)
        queue = collections.deque()
        queue.append(1)
        visited[1] = 1
        
        count = 1
        while queue:
            cur_node = queue.popleft()
            
            for next_node in graph[cur_node]:
                if not visited[next_node]:
                    queue.append(next_node)
                    visited[next_node] = 1
                    count += 1
        answer = min(answer, abs(n-count*2))
        
        # 와이어 복구
        graph[a].append(b)
        graph[b].append(a)
                
    return answer