[프로그래머스 Lv. 2] 전력망을 둘로 나누기

문제

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

접근

모든 edge를 하나씩 끊고 방문하지 않은 node에 대해 BFS를 사용하였다.
Union-Find 알고리즘을 사용하면 더 좋은 풀이일 것 같은데 기억도 안나고 해서 BFS로 풀었다.

중요한 점은 트리 형태로 연결되어 있다고 했는데, 트리 특성상 모든 Node가 Cycle이 없이 연결 되어 있다는 점. 이 조건이 반드시 어떠한 Edge를 끊어도 2개의 네트워크가 나온다는 것을 보증한다.

Code

from collections import defaultdict, deque

def solution(n, wires):
    def bfs(start,x,y):
        q = deque()
        q.append(start)
        dist[start] = 1
        curr=0
        cnt=1
        while q:
            curr = q.popleft()

            for next_num in graph[curr]:
                if curr == x and next_num==y or curr == y and next_num == x:
                    continue
                    
                if not dist[next_num]:
                    dist[next_num] = dist[curr]+1
                    q.append(next_num)
                    cnt+=1
        return cnt

    answer = 1000000
    graph = defaultdict(list)
    for wire in wires:
        a,b = wire
        graph[a].append(b)
        graph[b].append(a)

    for wire in wires:
        dist = [0] * (n+1)
        a, b = wire
        temp = []
        for i in range(1, n+1):
            if not dist[i]:
                max_dist = bfs(i,a,b)
                temp.append(max_dist)
        answer = min(answer, abs(temp[0]- temp[1]))
    return answer
  

여담

1. 이 문제는 작년 라X 코딩 테스트에서 봤던 문제다. 그 땐 트리라는 녀석에 쫄아서
   못 풀었지만 다시 풀어보니 10분 컷.

2. 위클리 챌린지 문제들은 풀어보는 것이 좋다. 프로그래머스 플랫폼을 통해 테스트를 진행했던 기업들에서 나온 문제들이라 어떠한 문제들이 나올지 예상은 할 수 있다. 수험생들로 비유하면 평가원 기출문제로 비유하면 될려나? ㅋㅋㅋ