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

😉 아이디어

1. 그래프의 엣지를 제거 후 남은 그래프 중 한 지점으로 뻗치는 엣지 개수 확인

2. _!전체 - 엣지 개수!_가 나머지 👉 이후 문제의 요구사항대로 최소값 산출

😉 풀이

towers = 0

def solution(n, wires):
    global towers
    graph = [[] for _ in range(n)]
    answer = 99_999
    # 그래프 그리기
    for wire in wires:
        x = wire[0] - 1
        y = wire[1] - 1

        graph[x].append(y)
        graph[y].append(x)
        
    # print(f'처음 만들어진 그래프 = {graph}')
                
    for wire in wires:
        visited = [0] * n
        x = wire[0] - 1
        y = wire[1] - 1
        
        # 엣지 제거
        graph[x].remove(y)
        graph[y].remove(x)
        
        # print(f'특정 엣지가 제거된 그래프 = {graph}')
        
        # 탐색 | 탐색 시작 자체가 타워 1
        towers = 1
        dfs(x, visited, graph)
        
        second_towers = n - towers
        result = abs(towers - second_towers)
        answer = min(answer, result)
        
        # 엣지 추가
        graph[x].append(y)
        graph[y].append(x)
        
    return answer

def dfs(start, visited, graph):
    global towers
    
    visited[start] = 1
    
    for node in graph[start]:
        if visited[node] == 0:
            dfs(node, visited, graph)
            towers += 1

✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/86971