프로그래머스[ LV2 | Python ] 전력망을 둘로 나누기

문제

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

풀이

변수로 주어지는 wires는 edge 정보를 담고 있다.
이를 이용해서 edge를 하나씩 끊어주고, bfs를 수행해 나뉘어진 네트워크에서의 노드 개수를 세어준다.

이 과정을 모든 엣지에 대해 수행하는데, 수행을 끝마치기 전에 끊어놓은 edge를 다시 되돌려 놓아야한다.

def solution(n, wires):
    from collections import deque
    answer = float('inf')
    wires = deque(wires)
    for c in range(len(wires)):
        board = [[] for _ in range(n+1)]
        cut = wires[c]
        wires[c] = []
        
        for w in wires:
            if w:
                x, y = w[0],w[1]
                board[x].append(y)
                board[y].append(x)
        
        v = [0]*(n+1)
        cnt = []
        for i in range(1,n+1):
            tmp = 0
            if not v[i]:
                v[i] = 1
                tmp+=1
                
            q = deque(board[i])
            while q:
                nx = q.popleft()
                if not v[nx]:
                    tmp+=1
                    v[nx] = 1
                    for k in board[nx]:
                        q.append(k)
            if tmp != 0:
                cnt.append(tmp)
        wires[c] = cut
        answer = min(abs(cnt[0]-cnt[1]), answer)
    return answer

생각 & 정리

전력선을 끊어주고, 다시 이어주는 과정을 모든 전력선에 대해 수행한다는 점에서 브루트 포스를 이용해야하는 문제라고 생각했다. 또한 그래프의 층이 깊지 않다고 생각해 bfs를 이용했다.

처음에는 어떻게 손 대야하는 문제인지 감이 잡히지 않았지만, 문제를 천천히 다시 읽고 주어진 정보에 대해서 곰곰히 생각해 보니 생각보다 쉽게 실마리가 보였다.

그렇다고해서 짧은 시간내에 푼 문제는 아니기 때문에, 정보를 빠르게 파악해야할 것 같다.