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

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

코딩테스트 연습 - 전력망을 둘로 나누기

전선을 하나씩 끊어 보며 bfs로 풀었다.

 

from collections import deque

def solution(n,wires):
    answer = 101
    for i in range(len(wires)):
        wire = wires[:i] + wires[i+1:]
        graph = [[] for _ in range(n+1)]
        visited = [False for _ in range(n+1)]
        for w in wire:
            graph[w[0]].append(w[1])
            graph[w[1]].append(w[0])
        queue = deque()
        queue.append((1))
        grid_count = 1
        visited[1] = True
        while queue:
            now = queue.popleft()
            for v in graph[now]:
                if visited[v] == False:
                    visited[v]=True
                    grid_count +=1
                    queue.append(v)
        answer = min(answer,abs(n-grid_count-grid_count))
    return answer