[Programmers] 전력망을 둘로 나누기 (완전탐색 - BFS Lv. 2) - Python

1. 문제

---

전력망을 둘로 나누기

2. 풀이

---

코드

from collections import deque

def bfs(start, graph):
    queue = deque()
    count = 1
    visited = [False] * len(graph)

    queue.append(start)
    visited[start] = True

    while queue:
        current = queue.popleft()
        if graph[current] is not None:
            for neighbor in graph[current]:
                if not visited[neighbor]:
                    queue.append(neighbor)
                    visited[neighbor] = True
                    count += 1
    return count

def solution(n, wires):
    min_diff = float('inf')
    graph = [[] for _ in range(n + 1)]

    for node1, node2 in wires:
        graph[node1].append(node2)
        graph[node2].append(node1)

    for node1, node2 in wires:
        graph[node1].remove(node2)
        graph[node2].remove(node1)
        diff = abs(bfs(node1, graph) - bfs(node2, graph))
        min_diff = min(min_diff, diff)
        graph[node1].append(node2)
        graph[node2].append(node1)

    return min_diff

입력 및 출력

n = 4
wires = [[1,2],[2,3],[3,4]]

>> 0

3. 로직

---

1. bfs(start, graph): 해당 함수는 너비 우선 탐색(BFS) 알고리즘을 구현한 함수이다. 시작 노드와 그래프를 입력으로 받아서 BFS를 수행하면서 시작 노드로부터 도달 가능한 노드의 개수를 세는 역할을 한다.
2. solution(n, wires): 이 함수는 전체 송전탑의 수 n과 전선 연결 리스트 wires를 입력으로 받는다. 해당 함수는 다음과 같은 과정을 거쳐 문제를 해결한다.

• min_diff 변수는 두 개의 분리된 전력망 네트워크의 송전탑 수 차이의 최소값을 추적한다.
• graph 리스트는 각 송전탑에 연결된 송전탑들을 저장하는 인접 리스트 형태의 그래프이다.
• wires 리스트의 각 전선 연결(node1, node2)에 대해 다음 과정을 수행한다.
  • graph에서 node1와 node2 사이의 연결을 제거한다.
  • bfs 함수를 호출하여 node1와 node2를 시작 노드로하여 각각의 전력망 네트워크에서 도달 가능한 송전탑의 개수 차이의 절댓값을 계산하고 min_diff와 비교하여 최소값을 업데이트 한다.
  • graph에 node1와 node2 사이의 연결을 다시 추가한다.
• 두 전력망이 가지고 있는 송전탑 개수의 차이의 최소값인 min_diff를 반환한다.

4. 그림

---