프로그래머스 - [Level 2] 전력망을 둘로 나누기 (파이썬)

https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=python3

프로그래머스

풀이

BFS + 완전탐색 방식의 풀이로 작성하였다. 각 연결을 하나씩 끊어보면서 두 전력망의 노드 수 차이의 최소값을 구하는 방식이다.

문제에서 요구하는 사항은

1. 하나의 연결을 끊어 전력망을 두개로 나누었을때,
2. 두 전력망 송전탑 개수 찾이의 최소값을 반환하는 문제이다.

BFS 코드는 너무 단순하기 때문에 간단하게 설명하면, 하나의 연결 그래프에서 시작 노드 S로부터 BFS를 수행하여 연결된 노드의 개수를 세는 함수로 칭한다.

전체적인 로직은 다음과 같다.

1. wires에서 하나의 간선을 끊어본다.
2. 끊어진 상태의 그래프를 만든다.
3. BFS를 통해 연결된 송전탑 수를 센다.
4. 반대편 송전탑 수는 n - count
5. 두 전력망의 차이의 최소값을 갱신한다.

시간 복잡도 분석

• O(E * (V + E))

코드

from collections import deque

def bfs(G, S, V) :
    queue = deque([S])
    V[S] = True
    count = 0
    while queue :
        v = queue.popleft()
        count += 1
        for i in G[v] :
            if not V[i] :
                queue.append(i)
                V[i] = True
    return count

def solution(n, wires):
    answer = n - 2
    for i in range(len(wires)) :
        tmps = wires.copy()
        G = [[] for i in range(n + 1)]
        V = [False] * (n + 1)
        tmps.pop(i)
        for wire in tmps :
            x, y = wire
            G[x].append(y)
            G[y].append(x)
        for index, graph in enumerate(G) :
            if graph != [] :
                S = index
                break
        counts = bfs(G, S, V)
        other = n - counts
        if abs(counts - other) < answer :
            answer = abs(counts - other)
    return answer

500등 안에 들때까지,,