99클럽 코테 스터디 24일차 TIL + 완전탐색

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

프로그래머스

from collections import deque

def bfs(v, n, trees):
    visited = [False for _ in range(n+1)]
    que = deque([v])
    visited[v] = True
    cnt = 1 # 이어져있는 전선의 송전탑 개수
        
    while que:
        now = que.popleft()
        for nxt in trees[now]:
            if visited[nxt] == False:
                visited[nxt] = True
                que.append(nxt)
                cnt += 1
    return cnt
    
def solution(n, wires):
    answer = n
    trees = [[] for _ in range(n+1)]
    
    for a,b in wires:
        trees[a].append(b)
        trees[b].append(a)
    
    for a,b in wires:
        # graph 선 자르기
        trees[a].remove(b)
        trees[b].remove(a)
        
        answer = min(abs(bfs(a,n,trees) - bfs(b,n,trees)), answer)
        
        # 다시 선 붙이기
        trees[a].append(b)
        trees[b].append(a)
    return answer

 

• 우선 trees라는 리스트를 만들어 각 송전탑이 연결되어있는 정보를 담은 리스트를 만든다.
• list.remove() 함수를 이용해 전선을 자르며 경우의 수를 구한다.
  • 이때, bfs를 이용해 연결되어 있는 송전탑 개수를 구한다.
• 해당 전선을 다시 붙이고 다음 전선을 자르기를 반복하며 가장 작은 값을 구한다.