[프로그래머스 Lv2.] 전력망을 둘로 나누기(python)

1. 문제

문제 설명

제한사항

입출력 예시

입출력 예 설명

---

2. 풀이 과정

내가 생각한 진행 과정

• 연결되어있는 송전탑을 확인한 다음, bfs를 이용해서 하나하나 전선들을 끊어가면서 두전력망이 가지고 있는 송전탑 갯수의 차이를 구한다.
  • n=9, wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]일 때,
    [[], [3], [3], [1, 2, 4], [3, 5, 6, 7], [4], [4], [4, 8, 9], [7], [7]]로 두어 연결되어있는 송전탑 확인
  • 1과 3을 끊음 -> [[], [], [3], [2, 4], [3, 5, 6, 7], [4], [4], [4, 8, 9], [7], [7]]
  • bfs를 이용해서 1번에 연결된 송전탑, 3에 연결된 송전탑 갯수 구하기
  • 다시 1과 3 연결
  • 계속 진행하면서 송전탑 갯수 차이 min값 구함

최종 코드

from collections import deque

def solution(n, wires):
    
    temp = [[] for _ in range(n+1)]
    for a,b in wires:
        temp[a].append(b)
        temp[b].append(a)
    # print(temp)
    
    def bfs(val):
        q = deque([val])
        cnt = 0
        visit = [0] * (n+1)
        visit[val] = 1

        while q:
            v = q.popleft()
            for i in temp[v]:
                if visit[i] == 0:
                    cnt += 1
                    visit[i] = 1
                    q.append(i)
        return cnt
    
    val_cnt = n
    for a,b in wires:
        temp[a].remove(b)
        temp[b].remove(a)
        val_cnt = min(abs(bfs(a) - bfs(b)), val_cnt)
        
        temp[a].append(b)
        temp[b].append(a)           
    # print(val_cnt)
    
    return val_cnt