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