프로그래머스 고득점 Kit - 전력망을 둘로 나누기

 

Problem

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

프로그래머스

• $n$ 개의 송전탑이 전선을 통해 하나의 트리로 연결되어 있다.
• 전선들 중 하나를 끊어 전력망 네트워크를 2개로 분할하려 한다.
• 이때, 두 전력망의 송전탑의 개수를 최대한 비슷하게 맞추고자 한다.
• 송전탑의 개수와 전선 정보가 주어질 때, 두 전력망이 가지고 있는 송전탑 개수 차이의 절댓값을 반환해라.

Input / Output Examples

n	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2.3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1

 

Solution

단순 무식하게 인접 리스트를 만들어주고, 끊을 전선을 기준으로 BFS를 돌려서 탐색한 노드의 차를 구했다.

그 다음 최솟값을 구하는 min 함수를 통해 기존 answer와 새로 구한 노드의 차 중 더 작은 값을 반환했다.

 

Code

from collections import deque

def bfs(tree, start, end):
    visited = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == end:
            continue
        if node not in visited:
            visited.append(node)
            queue.extend(set(tree[node]) - set(visited))
    return len(visited)

def solution(n, wires):
    answer = -1
    tree = dict()
    for a, b in wires:
        if a in tree:
            tree[a].append(b)
        else:
            tree[a] = [b]
        if b in tree:
            tree[b].append(a)
        else:
            tree[b] = [a]
    for wire in wires:
        a = bfs(tree, wire[0], wire[1])
        b = bfs(tree, wire[1], wire[0])
        if answer == -1:
            answer = abs(a-b)
        else:
            answer = min(answer, abs(a-b))
    return answer

 

Result

 

코드의 시간복잡도가 $O(n^3)$ 임에도 불구하고, 입력 크기인 $n$이 작아 생각보다 오래 걸리진 않은 것 같다.