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

from collections import deque

def bfs(n, tmp_graph, visited):
    q = deque([0])
    visited[0] = True
    
    while q:
        node = q.popleft()
        
        for next_node in tmp_graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                q.append(next_node)
    
    a, b = visited.count(True), visited.count(False)
    return abs(a-b)

def solution(n, wires):
    answer = 1e9
    
    for i in range(len(wires)):
        tmp_graph = [[] for _ in range(n)]
        visited = [False] * n
        for j in range(len(wires)):
            if i != j:
                a, b = wires[j][0]-1, wires[j][1]-1
                tmp_graph[a].append(b)
                tmp_graph[b].append(a)
        result = bfs(n, tmp_graph, visited)
        answer = min(answer, result)
        
    return answer

주어진 조건을 보면 n이 최대 100개이기 때문에 완전 탐색으로 해결 가능한 문제이다. 완전 탐색 방법은 주어진 전선에 대해 하나씩 뺀 상태로 bfs를 진행한다. 이렇게 되면 시간 복잡도는 간선에 대한 2중 for문 * bfs 시간 복잡도이므로 대략 n^3이다. 충분히 가능한 시간 복잡도이다.

2중 for문을 돌면서 간선 정보를 하나 뺀 graph를 저장한다.
이 graph를 가지고 bfs를 진행하면서 방문한 노드와 방문하지 못한 노드를 visited를 통해 구함으로써 2개로 분할된 노드의 개수 차이를 구할 수 있다.

이렇게 구한 노드의 개수 차이중 최소 값으로 정답을 구할 수 있다.