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

문제 설명

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

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

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
• wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 - v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
• 1 ≤ v1 < v2 ≤ n 입니다.
• 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

입출력 예

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

---

풀이
사실 전선을 하나보다 많이 끊는 조건이라면 백트래킹을 사용했어야하는 문제이다
그러나 딱 하나만 끊으면 되기 때문에 백트래킹까지 사용할 필요는 없고 단순히 선들을 돌아가면서 하나하나 끊어보면 된다
송전탑 개수를 셀 때는 bfs를 사용했다 한 송전탑을 시작으로 인접한 송전탑들을 찾아나가며 count를 세다가 더이상 인접한 송전탑이 없으면 종료한다
이 count가 둘 중 하나의 전력망의 송전탑 개수를 의미하기 때문에 n에서 count를 뺀 값이 나머지 전력망의 송전탑 수가 된다
따라서 굳이 bfs를 모든 점에 돌리거나 하는 일을 하지 않아도 된다

코드

from collections import deque
import sys

def solution(n, wires):
    answer = sys.maxsize
    for i in range(len(wires)):
        graph = [[] for _ in range(n+1)]
        edge_nums = []
        for j, edges in enumerate(wires):
            if i != j:
                u, v = edges
                edge_nums.append(u)
                graph[u].append(v)
                graph[v].append(u)

        q = deque()
        q.append(edge_nums[0])

        visited = [False]*(n+1)
        cnt = 1

        while q:
            cur = q.popleft()
            visited[cur] = True
            for elem in graph[cur]:
                if not visited[elem]:
                    q.append(elem)
                    cnt += 1

        answer = min(answer, abs(cnt-(n-cnt)))
    return answer