[프로그래머스/86971/level2/고득점kit] 전력망을 둘로 나누기 - 완전탐색, BFS

# 전선 없애면 [v1, v2] -> v1과 연결된 개수, v2와 연결된 개수 비교
# bfs로 -> 더이상 개수 셀게 없을 때 break
from collections import deque

def bfs(n, visited, tree, l):
    queue = deque([n])
    visited[n] = True
    cnt = 0

    while queue:
        v = queue.popleft()
        cnt += 1
        
        for i in range(1, l + 1):
            if tree[v][i] and not visited[i]:
                queue.append(i)
                visited[i] = True

    return cnt

            
def solution(n, wires):
    answer = n

    tree = [[False] * (n + 1) for _ in range(n + 1)]

    for v1, v2 in wires:
        tree[v1][v2] = True
        tree[v2][v1] = True

    for v1, v2 in wires:
        visited = [False] * (n + 1)
        
        #연결 끊기
        tree[v1][v2] = False
        tree[v2][v1] = False

        #bfs 돌고 개수 비교 
        answer = min(answer, abs(bfs(v1, visited, tree, n) - bfs(v2, visited, tree, n)))

        #원상복귀
        tree[v1][v2] = True
        tree[v2][v1] = True

    return answer