L2 : 전력망을 둘로 나누기 Python

L2 : 전력망을 둘로 나누기 Python

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

# dfs는 한 줄로 이어지는 경로 찾기와 같은 경우에 유리
# bfs는 되돌아갔다가 다른 경로를 찾는 등, 현재와 같은 문제에 유리
from collections import deque
def solution(n, wires):
    answer = n
    for yes, no in wires:
        visited = [0]*(n+1)
        dq = deque([yes])
        visited[yes], visited[no] = 1, 1 # 끊어진 곳을 방문했다고 처리하면 다시는 갈 수 없다.
        cnt = 1
        while dq:
            start = dq.pop()
            for a, b in wires:
                if a==start and visited[b]==0: # 시작점을 어디로 할지 고르는 과정. 도착점을 갈 수 있으면 append
                    dq.append(b)
                    visited[b] = 1
                    cnt += 1
                elif b==start and visited[a]==0:
                    dq.append(a)
                    visited[a] = 1
                    cnt += 1
        if answer > abs(n - 2*cnt): # 끊어지고 난 뒤, 두 전력망의 갯수 차이가 최솟값이 되면 갱신
            answer = abs(n - 2*cnt)
        
    return answer

#BFS