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

해당 글은 프로그래머스 Level2 '전력망을 둘로 나누기'을 다룬다.

문제

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

프로그래머스

 

설명

wires중 한 개의 전선을 지웠을때의 bfs를 각각 모두 구해서 두 개의 그래프의 노드 갯수 차이 절댓값이 작은 값을 return 해주었다. 또 다른 방법으로는 union-find 알고리즘을 통해 구해도 풀릴 것 같다.

 

코드

from collections import deque

def bfs(graph, start_node, visited, wire):
    queue = deque([start_node])
    visited[start_node] = True
    count = 1
    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if not ((node == wire[0] and i == wire[1]) or (node == wire[1] and i == wire[0])):
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True
                    count += 1
    return count

def solution(n, wires):
    answer = 1e9
    graph = [[] for _ in range(n+1)]
    for wire in wires:
        a, b = wire
        graph[a].append(b)
        graph[b].append(a)
    
    for wire in wires:      # 제외할 wire
        visited = [False] * (n+1)
        for i in range(1, n+1):
            if not visited[i]:
                count1 = bfs(graph, i, visited, wire)
                count2 = n - count1
                answer = min(abs(count1-count2), answer)
    return answer