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

문제 (LV.2)

https://programmers.co.kr/learn/courses/30/lessons/86971

 

코드

answer = 0


def bfs(wires, checked, num, cnt):
    global answer
    q = [num]
    while len(q) != 0:
        cur = q.pop(0)
        for i in range(0, len(wires)):
            if wires[i][0] == cur:
                if checked[wires[i][1]] == 0:
                    checked[wires[i][1]] = 1
                    q.append(wires[i][1])
                    cnt += 1
            elif wires[i][1] == cur:
                if checked[wires[i][0]] == 0:
                    checked[wires[i][0]] = 1
                    q.append(wires[i][0])
                    cnt += 1
    tmp_len = len(wires) + 1
    tmp = abs(cnt - (tmp_len - cnt))
    answer = min(answer, tmp)

    return answer


def solution(n, wires):
    global answer
    answer = 1000
    for i in range(0, n - 1):
        checked = [0 for _ in range(102)]
        checked[wires[i][0]] = 1
        checked[wires[i][1]] = 1
        bfs(wires, checked, wires[i][0], 1)

    return answer

 

 

해설

전력망은 위와같이 트리형태로 이루어져 있다는 점에서 BFS를 문제에 적용하였다.

BFS를 사용과 동시에 wires 리스트에 있는 모든 노드가 한번 씩 끊긴 경우를 판단하여 차이의 최솟값을 구해주어야 한다.

 

 

한 노드가 끊어진 경우에 두개의 트리가 나누어지게 되는데 이때, BFS를 한번 돌게되면

tmp = abs(cnt - (tmp_len - cnt))

위와같이 한쪽 트리의 전력망 갯수를 알게되면 나머지 하나의 트리의 전력망의 갯수도 알 수 있다.