99클럽 코테 스터디 2일차 TIL 프로그래머스 전력망을 둘로 나누기

오늘 주어진 문제는 전력망을 둘로 나누기 문제였다.

풀이

이번 문제도 1일차와 동일하게 완전탐색 알고리즘으로 풀 수 있는 문제였다.

주어진 wires의 간선을 하나씩 제외해보며, 체크해보고, 가장 차이가 작은 수를 출력하면 된다.

나는 BFS 알고리즘을 활용하여 1번 송전탑에 연결된 송전탑들을 센 후, 전체에서 빼서 비교한 다른 송전탑 집합과의 차이를 계속 비교하는 방법으로 쉽게 풀었다.

 

from collections import deque
def solution(n, wires):
    
    def bfs_and_difference(k):
        graph=[[] for _ in range(n)]
        visited=[False for _ in range(n)]
        for i in range(len(wires)):
            if i!=k:
                s,e=wires[i]
                graph[s-1].append(e-1)
                graph[e-1].append(s-1)
        queue=deque()
        queue.append(0)
        visited[0]=True
        while queue:
            num=queue.popleft()
            for next_num in graph[num]:
                if not visited[next_num]:
                    visited[next_num]=True
                    queue.append(next_num)
        side1=visited.count(True)
        side2=n-side1
        return abs(side1-side2)
    answer = 1e5
    for j in range(len(wires)):
        answer=min(answer,bfs_and_difference(j))
    return answer