title: "[프로그래머스] 전력망을 둘로 나누기 Python 파이썬 해설 (Level 2) - 이도훈"
cleanUrl: "programmers/86971"
description: "프로그래머스 Level 2 문제 [전력망을 둘로 나누기]의 풀이를 정리합니다."
best = -1
target = -1
from collections import defaultdict
def dfs(u, A, vis):
global best, target
s = 1
for v in A[u]:
if vis[v]:
continue
vis[v] = True
res = dfs(v, A, vis)
s += res
if abs(res-target) < abs(best-target):
best = res
return s
def solution(n, wires):
global target
target = n//2
A = defaultdict(list)
for u, v in wires:
A[u].append(v)
A[v].append(u)
vis = [False] * (n+1)
dfs(1, A, vis)
return abs(n - 2 * best)
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges