[프로그래머스 - Python3] 전력망 둘로 나누기

Solution

1. 송전탑과 연결된 간선은 이중 리스트를 활용해 트리로 나타낸다.

• 송전탑 번호 = 인덱스 번호
• 간선 = 그 인덱스에 들어있는 번호들

2. BFS를 활용하여 끊긴 노드를 제외하고 자신과 연결되어 있는 노드의 개수를 센다.

3. bfs를 돌리기 전 해당 노드를 미리 방문처리 하는 방식으로 간선을 끊는 걸 구현한다.

 

Code

from collections import deque
def solution(n, wires):
    answer = n
    # wires를 2차원 배열로 표현, 1번 송전탑부터 시작이기 때문에 n+1
    tree = [[] for _ in range(n+1)]
    # 송전탑 간의 간선을 트리로 구현
    for v1, v2 in wires:
        tree[v1].append(v2)
        tree[v2].append(v1)

    for start, split in wires:
        visited = [False] * (n+1)
        # bfs는 모든 노드를 순회하여 count를 세는 방식인데, 간선을 끊기 위해 split 노드를 이미 방문함으로 처리하여 bfs에 내에서 순회하지 않는 방식으로 간선을 끊었음.
        visited[split] = True
        cnt = bfs(start, visited, tree)
        if answer > abs(cnt - (n - cnt)):
            answer = abs(cnt - (n - cnt))
    return answer

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