문제

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

나의 코드

"""

"""

from itertools import combinations
from collections import deque
                
def solution(n, wires):
    
    def bfs(x):
        visited[x] = True
        connected_cnt = 1
        q = deque([x])

        while q:
            node = q.popleft()

            for i in graph[node]:
                if not visited[i]:
                    visited[i] = True
                    connected_cnt += 1
                    q.append(i)

        return connected_cnt

    cases = list(combinations(wires, len(wires)-1)) # 1개 끊은 결과
    answer = [] # 연결된 탑의 개수의 차이
    
    for case in cases:
        graph = [ [] for _ in range(n+1) ]
        visited = [False] * (n+1)
        
        for a, b in case:
            graph[a].append(b)
            graph[b].append(a)
        
        cnt_list = [] # 연결된 탑의 개수
        
        for i in range(1, n+1):
            if not visited[i]:
                cnt_list.append(bfs(i))
                
        answer.append(abs(cnt_list[0] - cnt_list[1]))
        
    return min(answer)
    

설명

완전탐색 + BFS 문제

참고 자료