전력망을 둘로 나누기

 

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

문제풀이

해당 문제는 dfs를 활용해서 푸는 게 효율적인 풀이방법이다.

 

• 지문을 보면 트리의 루트는 1부터 시작하며 크기는 n이다. 따라서 n 만큼의 크기를 가진 딕셔너리를 선언해 주고 각각 연결된 노드를 트리 형태의 그래프로 표현해 준다. 
• dfs를 실행하여 현재 노드의 연결되어 있는 자식 노드를 기준으로 깊이 탐색을 해준다. 그리고 재귀가 종료될 때마다 answer를 업데이트해 주는데 전체 간선의 개수는 n - 1이다 그중 전선을 하나 끊은 뒤 두 전력망의 노드 개수를 비교해야 하므로 현재 노드에서 특정 간선을 하나 끊었을 때 서브 트리의 크기와 기존 트리의 크기를 비교해준다.

def solution(n, wires):
    answer = float("inf")

    def dfs(current, parent):
        nonlocal answer
        size = 1
        for child in graph[current]:
            if child != parent:
                size += dfs(child, current)
        answer = min(answer, abs(n - 2 * size))
        return size

    graph = {i: [] for i in range(1, n + 1)}
    for x, y in wires:
        graph[x].append(y)
        graph[y].append(x)
    dfs(1, 0)
    return answer