[프로그래머스] Lv.2 전력망을 둘로 나누기 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/86971
• 🔑 완전 탐색, DFS
  • 전선 연결 지점 한 곳을 끊고 탐색 (끊긴 곳이면 가지 않음)
  • 이를 위해 양방향 그래프로 표현하고 해당하는 지점이면 continue
  • | 방문 한 곳 - 안 한 곳 | 이 가장 적은 값으로 정답을 계속 업데이트해 주면 끝 ✨

 

from collections import defaultdict

def solution(n, wires):
    answer = 1000
    
    graph = defaultdict(list)
    
    for i in wires:                 # 양방향 그래프
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])
    
    def dfs(node, remove_x, remove_y):
        
        for next_node in graph[node]:
            if visit[next_node] == 0:
                if (node == remove_x and next_node == remove_y) or (node == remove_y and next_node == remove_x):
                    continue            # 끊어야 할 전선이면 가지 않기
                else:
                    visit[next_node] = 1
                    dfs(next_node, remove_x, remove_y)
    
    for wire in wires:
        visit = [0] * (n+1)
        visit[1] = 1
        
        dfs(1, wire[0], wire[1])        # 1 부터 시작, 끊을 전선, 끊을 전선

        network1 = visit.count(0)-1     # 방문 안 한 곳
        network2 = visit.count(1)       # 방문 한 곳
        
        answer = min(answer, abs(network1 - network2))  # 차이가 가장 적은 케이스로 업데이트

    return answer