Level 2

문제

해당 문제 링크

정답

from collections import deque

def solution(n, wires):

    def bfs(start):
        visited=[0] * (n+1)
        q=deque([start])
        visited[start]=1
        cnt =1
        while q:
            s = q.popleft()
            for i in graph[s]:
                if not visited[i]:
                    q.append(i)
                    visited[i]=1
                    cnt+=1
        return cnt
    
    
    graph = [[] for _ in range(n+1)]
    for a, b in wires:
        #정점에 따라 연결되어있는 점들을 추가해줌
        graph[a].append(b)
        graph[b].append(a)

    res=n
    for a, b in wires: #전선을 하나씩 끊어봄
        graph[a].remove(b)
        graph[b].remove(a)
        
        # 두 쪽 전력망에 속한 송전탐의 개수를 세서 뺀다음 절댓값으로 나온 값 중 가장 작은 값이 답이다.
        res = min(abs(bfs(a) - bfs(b)), res) 
        
        graph[a].append(b)
        graph[b].append(a)

    return res

풀이

BFS를 이용해서 풀 것 같은 느낌은 있었지만, 어떻게 접근해서 풀어야할지 막막했다.
코드를 참고하며 이렇게 코드를 짜는 법이 있구나를 알며 문제를 풀어보았다.

풀이과정

크게 풀이 과정을 언급하자면,
이차원 그래프인 graph를 생성하고
하나의 송전탑을 기준으로 연결되어있는 송전탑들을 맞게 넣어준다.

graph = [[] for _ in range(n+1)]
    for a, b in wires:
        #정점에 따라 연결되어있는 점들을 추가해줌
        graph[a].append(b)
        graph[b].append(a)

예시 1을 기준으로 아래와 같이 graph에 담긴다.

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

이후,
전선을 하나씩 끊어서 둘로 나눠진 송전탑을 BFS()를 써서 센다.
두 쪽 전력망에 속한 송전탐의 개수를 세서 뺀다음 절댓값으로 나온 값 중 가장 작은 값이 답이다.
끊은 전선은 다시 연결하고, 하나씩 비교해서 가장 작은 값을 도출해내는 것이다.