[python] 전력망을 둘로 나누기

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

---

defaultdict에 노드별로 모든 엣지의 경우들을 정리한 후에 dfs를 안 쓰고

노드 수가 1인 leaf 노드부터 다 쳐내고 맨 마지막에 남는 노드가 간선이 잘리는 루트 노드라는 걸 이용해서 풀려고 했는데

거기에서 결국 서로 연결된 노드를 저장하고 길이를 구하려면 dfs가 되지 않나...? 라는 생각에 dfs로 돌아갔다

dfs + 트리 문제는 다시 풀어보기

 

 

import collections
 
def solution(n, wires):
    if n <= 1 :
        return 0
    result = float('inf')
    graph = collections.defaultdict(list)
    for a, b in wires:
        graph[a].append(b)
        graph[b].append(a)
 
    def dfs(x, visited):
        visited.add(x)
        for v in graph[x]:
            if v not in visited:
                dfs(v,visited)
        return visited
 
    for i in graph:
        for j in graph[i]:
            nodes = set()
            nodes.add(i)
            visited = dfs(j, nodes)
            diff = abs(n - (len(visited) - 1) - (len(visited)-1)) # (전체 간선 수 - 자른 후 한쪽 트리의 길이 - 잘린 간선 1) - 다른 쪽 트리의 길이 - 잘린 간선 1
            result = min(result, diff) # 모든 수를 계산하여 최소값을 구함
    return result