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

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

코딩테스트 연습 - 전력망을 둘로 나누기

 

• 해설 :

트리형태로 연결되어있는 전력망이 있다. 트리의 간선들 중 하나를 끊어 두 개의 트리로 나눈다고 할 때, 이 두 트리의 노드 개수의 차이가 최소가 되는 값을 찾으면 된다 

 

 

 

• 풀이 :

트리의 탐색은 BFS로 진행했지만 전체적인 구조는 완전탐색으로 진행하였다. 간선들의 정보가 주어진 wires 배열에서 인덱스별로 하나씩 삭제하는 경우를 copy하여 bfs로 탐색하였고 각 경우마다 최솟값을 매 번 갱신해주었다.

BFS를 구현할 때 탐색을 무조건 2 번만 실행하게 구현하였는데 이는 트리라는 구조의 특징 때문이다. 트리는 모든 노드 사이의 간선이 있으므로 그 간선들 중 하나를 끊는다면 반드시 두 개의 트리로 나누어진다는 것이 보장된다. 따라서 BFS를 두 번만 실행하면 반드시 모든 노드를 탐색하게 되고, 이 탐색결과 사이의 차이값을 최솟값으로 갱신해주면 된다.

 

 

 

 

from collections import deque
 
def check(board,a1,a2,n):
    bor = [[] for _ in range(n+1)]
    c = [0 for _ in range(n+1)]
    cnt1,cnt2 = 0,0
    for x,y in board:
        bor[x].append(y)
        bor[y].append(x)
    queue = deque()
    c[a1] = 1
    queue.append(a1)
    while queue:
        x = queue.popleft()
        for i in bor[x]:
            if c[i] == 0:
                queue.append(i)
                c[i] = 1
                cnt1 += 1
    queue = deque()
    c[a2] = 1
    queue.append(a2)
    while queue:
        x = queue.popleft()
        for i in bor[x]:
            if c[i] == 0:
                queue.append(i)
                c[i] = 1
                cnt2 += 1
    return abs(cnt1-cnt2)
 
def solution(n, wires):
    answer = 1000
    for i in range(len(wires)):
        a1,a2 = wires[i]
        board = wires.copy()
        del board[i]
        answer = min(answer,check(board,a1,a2,n))
    return answer