1. 문제 설명
- 문제 링크
- n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
n은 2 이상 100 이하인 자연수입니다.
wires는 길이가 n-1인 정수형 2차원 배열입니다.
wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
1 ≤ v1 < v2 ≤ n 입니다.
전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.
2. 풀이
- 트리 형태로 연결되어 있고, 결국 그래프 형태와 같다.
- 주어진 wires들을 이용해 그래프 -> 트리 형태를 먼저 만든다.
- MakeTree
- 1번 노드 부터 탐색해 나가면서 중복 엣지를 없엔다.
- MakeTree
- 하나로 이어진 그래프에서 각 노드의 자식개수를 계산한다.
- Count
- 역시 1번 노드 부터 시작해 자식의 개수를 센다.(재귀)
- Count
- 마지막으로 총 개수에서 각 노드의 자식의 개수를 뺀 차이가 가장 작은 값을 선택한다.
3. 코드
- python
from collections import deque
def Count(v):
global graph
global numofChild
if numofChild[v] != -1:
return numofChild[v]
count = len(graph[v])
for child in graph[v]:
count += Count(child)
numofChild[v] = count
return count
def MakeTree(n):
global graph
q = deque()
q.append(1)
while q:
now = q.popleft()
for new in graph[now]:
q.append(new)
graph[new].remove(now)
return
graph = []
numofChild = []
def solution(n, wires):
global graph
global numofChild
graph = [[] for _ in range(n + 1)]
numofChild = [-1 for _ in range(n + 1)]
for v1, v2 in wires:
graph[v1].append(v2)
graph[v2].append(v1)
MakeTree(n)
Count(1)
return min(map(lambda x: abs((n-(x + 1))-(x + 1)), numofChild))
4. 결과 및 회고
생각 보다 오래걸렸다. 아직 파이썬 전역변수 스코프에 대해 헷갈리는 부분이 있는 것 같다. 다시 한번 공부를 해야할 것 같다.
되도록이면 전체적으로 쓰는 변수에 꼭 global을 붙여서 사용해야겠다.