[프로그래머스 - 86971]. 전력망 둘로 나누기

[프로그래머스 - 86971]. 전력망 둘로 나누기

from collections import deque

MAX = 101
visited = []
def init_graph(graph):
    _graph = [[] for _ in range(len(graph) + 3)]
    
    for a, b in graph:
        _graph[a].append(b)
        _graph[b].append(a)
        
    return _graph

def bfs(graph):
    global visited
    answer = []
    for start in range(1, len(graph)):
        q = deque([start])
        cnt = 0
        
        while q:
            node = q.popleft()
            visited[node] = True
            cnt += 1
            
            for next in graph[node]:
                if visited[next]: continue
                visited[next] = True
                q.append(next)
                
        if cnt != 1:
            answer.append(cnt)
            
    return answer

def solution(n, wires):
    global visited
    answer = MAX
    # 간선 하나를 제외한 인접 그래프 생성
    for rm_idx in range(n - 1):
        cpy_wires = wires[:]
        cpy_wires.pop(rm_idx)
        
        graph = init_graph(cpy_wires)
        # # BFS로 노드 개수 구하기
        visited = [False for _ in range(n + 1)]
        
        cnt = bfs(graph)
        
        if len(cnt) == 2:
            answer = min(answer, abs(cnt[0] - cnt[1]))
        
    return answer if answer != MAX else n - 2

범위

• 2 ≤ N(송전탑 개수) ≤ 100

• wires : n - 1

풀이

• 간선 하나를 잘라서 두 개의 그래프로 쪼갠 후, 각 그래프 간 노드의 최소 차이를 구하는 문제
1️⃣. wires를 반복하며 간선 하나씩을 제외한 리스트를 파라미터로 init_graph호출
→ init_graph : 주어진 간선 리스트를 바탕으로 인접 리스트 생성 메서드
2️⃣. init_graph 에게 리턴 받은 인접 리스트로 BFS 진행
→ 1 ~ N 까지의 노드를 시작노드로 BFS 진행해서, 각각의 노드 개수를 answer에 담아 리턴
3️⃣. 리턴받은 answer중 차이 값이 가장 작은 값을 출력
answer if answer != MAX else n - 2
• bfs 함수에서 cnt가 1이 아닐 때만 answer에 담아주는데, cnt가 1일 경우에 자기 자신만 포함된 네트워크여서 그렇게 해줬습니다.
• 따라서 answer가 초기값인 MAX인 경우,
주어진 테케의 최솟 값은 1과, (N - 1)의 개수를 가지는 네트워크이므로, N - 2가 됩니다.