[프로그래머스] 전력망 둘로 나누기 / 완전탐색 / python

문제

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

프로그래머스

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.

 

• 4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.
• 또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.

풀이

아이디어

끊을 수 있는 모든 간선을 끊은 후 두 전력망의 송전탑의 개수가 최대한 비슷할 때 차이를 return하도록 한다

 

트리를 이차원 배열로 나타낸다

양방향 트리이므로 이차원배열에 대칭 되도록 넣는다

 

👏🏻할일

• 그래프 표현, 전체 가능한 경우의 수 확인
• BFS를 이용해 연결된 송전탑 확인
• 송전탑 수 비교, 최소 차이값으로 업데이트

 

 

코드

BFS 풀이

from collections import deque
def solution(n, wires):
    answer = n
    # 트리 표현 (1<= <= n), 양방향
    tree = [[] for _ in range(n+1)]     
    for a, b in wires:
        tree[a].append(b)
        tree[b].append(a)

    # 순서대로 간선 끊기
    for start, split in wires:
        visited = [False] * (n+1)
        visited[split] = True
        cnt = bfs(start, visited, tree)

        if abs(cnt - (n-cnt)) < answer:
            answer = abs(cnt - (n-cnt))


    return answer

def bfs(start, visited, tree):
    # 송전탑의 개수
    cnt = 1
    q = deque([start])
    visited[start] = True

    while q:
        v = q.popleft()
        for i in tree[v]:
            if  visited[i]:
                continue
            q.append(i)
            cnt += 1
            visited[i] = True
    return cnt