전력망을 둘로 나누기 - 파이썬(python)

 

BFS 에 익숙치 않아 많은 시간이 소요된 문제...

아래 영상이 기본 개념 숙지에 많은 도움이 되었다.

 

 

나의 풀이

from collections import deque

def bfs(start, visited, graph) :
    cnt = 1
    visited[start] = True
    queue = deque([start])
    
    while queue :
        v = queue.popleft()
        for i in graph[v] :
            if not visited[i] :
                queue.append(i)
                visited[i] = True
                cnt += 1
                
    return cnt

def solution(n, wires):
    graph = [[] for _ in range(n+1)]
    count = []
    
    for a,b in wires :
        graph[a].append(b) 
        graph[b].append(a)
    
    for start_node, cut_node in wires :
        visited = [False] * (n+1)
        visited[cut_node] = True 
        cnt = bfs(start_node, visited, graph)
        count.append(abs(cnt-(n-cnt)))
        
    return min(count)

step 1

• 위 문제는 연결된 간선의 쌍 [v1, v2] 이 input 으로 주어졌다.
• 이를 쉽게 풀기 위해 많은 BFS 에서 제공되는 input 의 형태로 변경하였다.
• -> [[], [1번 노드와 연결된 노드들의 집합], [2번 노드와 연결된 노드들의 집합], ... ] 
• -> [a,b] 의 간선은 graph 의 a번째 인덱스에 b를 추가하며, graph의 b번째 인덱스에 a를 추가하였다.

step 2

• wires 중 하나의 전선을 끊기 위해서 for 문으로 하나의 전선씩 끊는다.
• 끊겨진 전선 중 한쪽 노드를 시작노드로 하여 BFS 문을 돌면서 visited[i] 가 false 인 노드들을 방문한다.

• 위와 같은 그래프에서 [4,7] 의 간선을 끊는다고 가정하자. 이때는 끊겨진 그래프 중 한 쪽 그래프만 탐색하여 연결된 노드들의 개수를 센다면, n-(한쪽 그래프 노드 개수) 가 다른 쪽 그래프의 노드 개수가 될 것이므로, 한 쪽만 탐색하면 된다.
• 따라서 [4,7] 의 경우 앞에 있는 4를 start_node(시작 노드) 로 간주하고, 7을 cut_node (끊긴 노드) 로 간주한다.
• cut_node 의 경우, visited[i] 를 True 로 변경하여, 방문하지 못하도록 한다.
• 이제, bfs(start_node, visited, graph) 를 실행한다.

step 3

• 시작 노드를 방문하므로 cnt = 1로 초기화하며, visited[start] = True 로 변경한다.
• 그런다음, collections 모듈의 deque 를 사용하여 시작 노드가 들어간 리스트 형태의 deque 를 생성한다.
• ★ pop(0)와 같은 함수를 수행할 때 리스트의 경우 O(N)연산을 수행하지만 deque는 O(1) 연산을 수행한다.
• 큐가 빌 때까지 노드들을 방문하는 과정을 계속한다.
• 먼저, queue.popleft() 로 맨 앞에 있는 가장 오래된 노드를 꺼낸다.
• graph[v] 안에 있는 원소들 (v 노드와 인접한 원소들) 을 탐색하면서, visited[i] = False 라면, 해당 노드를 queue 에 넣고 방문한다 (visited=True 로 변경).
• 이렇게 BFS 는 해당 원소와 인접한 방문하지 않은 노드들을 모두 탐색하는 방법이다.
• 더 이상 방문할 수 있는 노드가 없다면, cnt (노드 개수) 를 리턴하며 bfs 함수는 종료된다.

step 4

• 반환된 cnt 는 분할된 한 쪽 그래프의 노드 개수이다. 따라서 절댓값 함수 abs 를 이용해 abs(cnt - (n-cnt)) 로 두 그래프의 노드 개수 차이를 count 리스트에 추가한다.
• 모든 간선을 탐색하며 하나씩 끊는 경우를 완료했을 때, count 리스트에서 가장 최솟값이 정답이 될 것이다.