https://programmers.co.kr/learn/courses/30/lessons/86971?language=python3

문제 설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

풀이

완전 탐색으로 선을 하나씩 끊어가며 확인해보겠다는 아이디어는 맞았다.
하지만 문제는 dfs로 어떻게 노드의 개수(전력망의 개수)를 구하는지가 어려웠다.
lv.2 문제 이지만 그래프 탐색 부분이 아직 약한거 같다 ㅠ

wires를 인접리스트로 만들고
선을 하나씩 끊는다
그리고 끊은 노드에 각각 dfs를 돌리면 각각의 그룹의 노드 개수가 나오게 된다
예를 들어 [1,3]의 wire를 끊으면
dfs(1) => 그룹1(노드1이 포함된 그룹) 의 노드개수
dfs(3) => 그룹2(노드3이 포함된 그룹) 의 노드개수
가 된다.
끊은 선은 다시 복구하여
노드개수의 차이를 정답 리스트에 넣고
가장 작은 수를 리턴하면 된다.

DFS

노드 개수를 구할때
먼저 방문 표시를 해주고
node를 1정의 해준다
인접리스트의 here번째의 있는 요소들을 검사하여서
방문하지 않았으면 방문하게 되는데 이때 마지막에 노드를 리턴하면서 노드를 하나씩 축적하여
방문한 노드의 개수를 셀 수 있다.
이 방법 꼭 기억해놓자!

소스코드

import math
def dfs(here):
    visited[here] = 1
    node = 1
    for i in graph[here]:
        if visited[i] == 0:
            node += dfs(i)
    return node
            
def solution(n, wires):
    answer = -1
    global graph
    graph = [[] for _ in range(n+1)]
    global visited
    visited = [0]*(n+1)
    for w in wires:
        graph[w[0]].append(w[1])
        graph[w[1]].append(w[0])
    ans_list = []
    for w in wires:
        visited = [0]*(n+1)
        # 단선
        graph[w[0]].remove(w[1])
        graph[w[1]].remove(w[0])
        # 그룹1 노드 개수
        group1 = dfs(w[0])
        # 그룹2 노드 개수
        group2 = dfs(w[1])
        gap = abs(group1 - group2)
        ans_list.append(gap)
        
        # 선복구
        graph[w[0]].append(w[1])
        graph[w[1]].append(w[0])
        
    Min = math.inf
    for a in ans_list:
        if Min >= a:
            Min = a
    return Min