def solution(n, wires):
from collections import deque #자료구조를 불러옴
def bfs(start, graph, visit): #넓이우선 탐색을 한다
queue = deque([start])
visit[start] = True
count = 1 # 시작 노드 포함
while queue:
node = queue.popleft() #popleft로 맨 앞을 제거하며 반환한다
for n in graph[node]:
if not visit[n]:
visit[n] = True
queue.append(n)
count += 1
return count
min_diff = n # 초기값은 최대값으로 설정
for cut in wires:
# 그래프 초기화하기
graph = [[] for _ in range(n + 1)] #노드 번호를 1부터 n까지
# 하나를 끊음
for wire in wires:
if wire == cut:
continue
a, b = wire
graph[a].append(b)
graph[b].append(a)
# 두 송전탑 그룹의 크기 구하기
visit = [False] * (n + 1)
count = bfs(1, graph, visit) # 랜덤으로 탐색 시작
diff = abs(n - count - count) # 차이를 계산한다
min_diff = min(min_diff, diff) # 최소값을 업데이트 한다
return min_diff
