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

programmers > 코딩테스트 연습 > 위클리 챌린지 > 전력망을 둘로 나누기 

문제 링크

코딩테스트 연습 - 전력망을 둘로 나누기

 

풀이 코드

주어진 입력 트리에서 간선 하나를 끊어 두개의 그룹으로 나눈다. 그리고 나눠진 그룹간의 노드 수 차이가 가장 적은 값을 찾는 문제이다. 이 문제에서는 송전탑의 개수 n의 최댓값이 100이기 때문에(숫자가 작아서) 모든 간선을 하나씩 끊어보고 dfs로 정답을 찾았다. 

from collections import defaultdict


def dfs(start, visit):
    global cnt
    visit.append(start)
    cnt += 1
    for i in tree[start]:
        if i not in visit:
            dfs(i, visit)


def solution(n, wires):
    global tree, cnt
    tree = defaultdict(list)
    answer = 1e9
    
    for x, y in wires:
        tree[x].append(y)
        tree[y].append(x)
    
    for x, y in wires:
    	# 끊을 전선
        tree[x].remove(y)
        tree[y].remove(x)
        
        # 끊은 전선을 시작점으로 해서 dfs를 돌려본다
        cnt = 0
        dfs(1, [])
        
        answer = min(answer, abs(n - (cnt*2)))
        
        # 끊은 전선 복구
        tree[x].append(y)
        tree[y].append(x)
        
    return answer