[프로그래머스/Level2] 전력망을 둘로 나누기 (Python)

 

문제 설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.

 

입출력 예

n	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1

 

---

 

문제 풀이

💡 접근 방법

• `wires`를 딕션너리로 생성
• `wires`를 반복하며 하나씩 끊음
  • `q` 반복하며 끊긴 전선이 아니고 
  • 전선 `1`이랑 연결된 전선 구해서 `check_list`에 추가

✏️ 풀이 코드

from collections import deque
         
def solution(n, wires):
    answer = float("inf")
    
    # 그래프 생성
    g = {}
    
    for w1, w2 in wires:
        if w1 not in g:
            g[w1] = []
        if w2 not in g:
            g[w2] = []
            
        g[w1].append(w2)
        g[w2].append(w1)
        
    # BFS
    for w1, w2 in wires:
        
        q = deque()
        q.append(1)
        check_list = [0] * n

        while q:
            start_node = q.popleft()
            check_list[start_node - 1] = 1

            for target in g[start_node]:
                if (start_node == w1 and target == w2) or (start_node == w2 and target == w1):
                    continue
                    
                if check_list[target - 1] == 1:
                    continue
                    
                q.append(target)

        count_one = check_list.count(1)
        count_zero = n - count_one
        answer = min(answer, abs(count_one - count_zero))
        
    return answer

 

---

 

🔗 문제 출처

프로그래머스