프로그래머스 - 전력망을 둘로 나누기 (BFS + 완전탐색)

2차원리스트로 각 노드의 연결정보가 주어지고,

연결된 트리노드를 한곳 절단했을 때 두 트리의 노드수 차이가 최소가 되도록 하고 그 차이를 return하는 문제이다.

 

문제를 보자마자 생각했던 흐름은

 

하나의 연결(원소 pop하기)을 빼고, 딕셔너리에 저장한 뒤 BFS로 해당 트리의 노드개수를 계산하고 차이를 업데이트 한다.

였다.

 

한쪽 트리만 해줘도 되는 이유는 5개의 노드에서 한트리가 3개라면 나머지하나는 자동으로 2가되고 차이도 당연히 알 수 있기 때문이다.

 

for문으로 크게 감싸 i번쨰 원소를 pop해주고 위의 로직대로 진행해준다.

쉬운 문제.

 

from collections import defaultdict, deque

def bfs(graph):
    queue = deque()
    visited = set()
    queue.append(1)
    
    while queue:
        curr_node = queue.popleft()
        if curr_node not in visited:
            visited.add(curr_node)
            queue.extend(graph[curr_node])
    
    return len(visited)
            

def solution(n, wires):
    part = 0
    answer = 987654321
    
    for i in range(n):
        i_wires = wires[:i] + wires[i+1:]
        graph = defaultdict(list)
        for a, b in i_wires:
            graph[a].append(b)
            graph[b].append(a)
        
        part = bfs(graph)
        if answer > abs(n - part - part):
            answer = abs(n - part - part)
    
    return answer