[프로그래머스] 전력망을 둘로 나누기 (level2, python)

 

 

---

 

🤔 풀이 코드

 

import copy
from collections import deque

def bfs(start, tree, n):
    visited = [False for _ in range(n+1)]
    queue = deque()
    queue.append(start)
    visited[start] = True
    result = 1
    
    while queue:
        now = queue.popleft()
        for next_node in tree[now]:
            if not visited[next_node]:
                queue.append(next_node)
                visited[next_node] = True
                result += 1
                
    return result

def solution(n, wires):
    answer = n
    adjust_arr = [[] for _ in range(n+1)]
    
    for wire in wires:
        a, b = wire
        adjust_arr[a].append(b)
        adjust_arr[b].append(a)
        
    for cut_wire in wires:
        cuta, cutb = cut_wire
        copied_arr = copy.deepcopy(adjust_arr)
        copied_arr[cuta].remove(cutb)
        copied_arr[cutb].remove(cuta)
        
        answer = min(answer, abs(bfs(cuta, copied_arr, n) - bfs(cutb, copied_arr, n)))
        
    return answer

 

 

🤔 풀이 설명

 

풀이가 굉장히 길지만, 크게 어렵지 않습니다.

문제에서 주어진 송전탑의 개수는 기껏해야 100개, 전선의 수는 최대 99개입니다. 

전력망을 하나씩 끊어보고, 끊은 경우의 양 네트워크의 노드 수를 세기만 하면 되는 문제입니다.

 

우선, 인접 배열로 만들어주고, cut_wire 부분에서 자를 전선을 고릅니다.

2차원 배열의 내부까지 깊은 복사를 진행하기 위해서 deepcopy를 사용합니다.

자른 이후에, cuta와 cutb는 각각 bfs의 첫 시작지점이 될 수 있으므로 이 점을 유의합니다.