프로그래머스(programmers) 전력망을 둘로 나누기 python 정답 [완전 탐색]

프로그래머스(programmers) 전력망을 둘로 나누기 python 정답 [완전 탐색]

문제 링크

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

문제 정답

입출력 예

문제 이미지

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

정답 코드

from collections import deque
def bfs(start,visitied,graph):
    queue = deque([start])
    result = 1
    visitied[start] = True
    while queue:
        now = queue.popleft()        
        for i in graph[now]:
            if visitied[i] == False:
                result += 1
                queue.append(i)
                visitied[i] = True
                
    return result
        

def solution(n, wires):
    answer = n
    graph = [[] for _ in range(n+1)]
    
    for v1,v2 in wires:
        graph[v1].append(v2)
        graph[v2].append(v1)
            
    for start,not_visit in wires:
        visitied = [False]*(n+1)
        visitied[not_visit] = True
        # 한 쪽만 탐색
        result = bfs(start,visitied,graph)
        answer = min(answer,abs(result - (n-result)))
        
    return answer

문제 해설

이 문제는 항상 전력망이 2개로 나뉜다 가정한다.

이 경우 한쪽 전력망을 전부 방문하면 남는 전력망은 다른 전력망이 된다.

따라서 모든 노드를 시작점으로 bfs를 시도한 뒤, bfs로 연결한 노드의 수를 전체 갯수에서 빼면 다른 전력망의 노드 수가 나온다.

이 두개의 차 abs(result - (n-result))의 최솟값(min)을 갱신하면 된다.