[프로그래머스] 위클리 챌린지_9주차_전력망을 둘로 나누기

📕 문제

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

코딩테스트 연습 - 9주차

 

💡 풀이법

: 트리 문제이기 때문에 dfs, bfs일거라고 생각했다. 보통 bfs가 dfs보다 빠르기 때문에 bfs를 선택했다.

어떤 선을 끊어야 할까 어떻게 바로 찾을 수 있지 생각하다가 완전 탐색으로 접근했다.

즉, 모든 선을 끊어보고 두 트리의 노드 개수 차이의 절대값이 작은 것을 택하는 방법이다.

 

1. wires 리스트를 돌면서 전선 정보를 하나씩 없애고 bfs를 돌린다.

2. visited에 방문한 노드들을 담는다. 담기지 않은 노드들은 다른 트리의 노드이다.

 

(bfs를 어떤 노드 부터 시작하지 고민하다가 사실 어떤 노드든지 상관없다고 생각해서 마지막 n1을 넣어줬다.

단, 없앤 전선 정보에 유일하게 들어있던 노드를 넣으면 안된다.

예를 들어

wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]

이 상황에서 맨 앞의 전선 정보를 없앴는데 bfs(1)을 돌려버리면 1에 대한 정보가 없어진 상태이기 때문에 에러가 남.)

 

3. 이렇게 모든 전선을 끊어보며 bfs를 돌리고 그때마다 노드 개수 차이를 answer와 비교해주며 더 작은 값을 answer에 저장한다.

 

from collections import deque, defaultdict
    
def solution(n, wires):
    def bfs(n):
        deq = deque()
        deq.append(1)
        visited.append(1)

        while deq:
            v = deq.popleft()
            for i in node[v]:
                if i not in visited:
                    deq.append(i)
                    visited.append(i)
                
    answer = 99999
    n1 = 0
    for i in range(len(wires)):
        node = defaultdict(list)
        for item in wires[:i]+wires[i+1:]:
            n1, n2 = item
            node[n1].append(n2)
            node[n2].append(n1)
        visited=[]
        bfs(n1)
        answer = min(answer, abs(len(visited)-(n-len(visited))))
    return answer