[PG/Python] 전력망을 둘로 나누기

📌 문제

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

코딩테스트 연습 - 전력망을 둘로 나누기

 

📌 문제 접근 방법

1. 인접리스트를 활용해서 연결된 전선 정보를 입력해준다.
2. wires를 한 번 더 반복문을 돌리면서 전선들 중 하나를 끊는다.
3. 이 때 끊긴 두 송전탑을 기준으로 전력망이 가진 송전탑의 개수를 bfs를 활용해서 구해준다.
4. 두 전력망의 송전탑 수와 현재의 answer에 저장된 값을 비교하여 더 작은 값으로 answer 값을 갱신해준다.
5. 끊긴 두 송전탑을 다시 연결해주고 다음 전선으로 넘어간다.

 

📌 코드

from collections import deque

def bfs(v, n, grid):
    cnt = 0
    
    queue = deque()
    queue.append(v)
    
    visited = [0 for _ in range(n+1)]
    visited[v] = 1
    
    while queue:
        v = queue.popleft()
        
        for w in grid[v]:
            if not visited[w]:
                visited[w] = 1
                queue.append(w)
                cnt += 1
    
    return cnt


def solution(n, wires):
    global answer
    
    # 인접 리스트
    grid = [[] for _ in range(n+1)]
    
    for i in range(n-1):
        grid[wires[i][0]].append(wires[i][1])
        grid[wires[i][1]].append(wires[i][0])
    
    # 하나씩 연결을 끊고 개수 확인
    for i in range(n-1):
        grid[wires[i][0]].remove(wires[i][1])
        grid[wires[i][1]].remove(wires[i][0])
            
        cnt_node1 = bfs(wires[i][0], n, grid)
        cnt_node2 = bfs(wires[i][1], n, grid)
        
        answer = min(answer, abs(cnt_node1 - cnt_node2))
        
        grid[wires[i][0]].append(wires[i][1])
        grid[wires[i][1]].append(wires[i][0])
    
    return answer


answer = float('inf')