완전탐색 Level 2 전력망을 둘로 나누기 - python (프로그래머스)

소스 코드

from collections import deque

def make_graph(n, wires):
    # 트리형태를 그래프로 표현
    graph = [[] for _ in range(n+1)]
    
    for node,neighbor in wires:
        graph[node].append(neighbor)
        graph[neighbor].append(node)
    
    return graph

def solution(n, wires):
    
    answer_list = []
    graph = make_graph(n, wires)
    

    def bfs(graph, start, visited):
        count = 1
        visited[start] = True
        queue = deque([start])
        while queue:
            node = queue.popleft()
            
            for neighbor in graph[node]:
                if visited[neighbor] == False:
                    count += 1
                    queue.append(neighbor)
                    visited[neighbor] = True
        return count
                    
    for start, cut_wire in wires:
        visited = [False] * (n+1)
        visited[cut_wire] = True
        tower_count = bfs(graph, start, visited)
        
        answer_list.append(abs(tower_count - (n-tower_count)))
    
    
    return min(answer_list)

 

풀이

위 문제도 역시 처음에는 bfs/dfs를 사용할 용기조차 얻지 못하였다. 그만큼 탐색 문제에 대해서 너무 거부감을 느끼고 있었다 ㅠㅠ

그래도 차근차근 기초적인 bfs/dfs 템플릿을 달달 외우고 다시 도전하였다.

 

처음에 제일 힘들었던 부분은 bfs를 사용해야 한다는 것과 그래프를 일일이 하나씩 끊어보며 찾아본다 이부분은 알겠는데 어떻게 시작해야 할 지 정말 막막했다. 하지만 알고리즘 문제 책에서 나와있는 예제와 비교해보고, 힌트를 찾아가며 해당 문제에 대해 이해가 되기 시작했다.

 

먼저 그래프를 만드는 부분이다. 송전탑은 1부터 시작하기 때문에 wires의 길이보다 1 크게 만들어서 1부터 시작 가능하도록 하였고 각 위치에는 해당 송전탑과 연결되어 있는 송전탑의 번호를 채워 넣었다.

 

그 다음에는 bfs를 호출할 때 그래프를 어떤 방식으로 끊어서 넘겨줄지 이다. 위 코드에서는 for 문을 돌며 끊어진 송전탑 부분에는 visited를 True로 바꿔주는 방식을 택하였다. bfs 함수 내에서는 연결된 송전탑들을 모두 순회해가며 개수를 카운팅 하고 종료 이후에 나눠진 전력망의 송전탑 개수 차를 구하고 그에 대한 절대값을 구한다. 해당 값을 answer_list에 저장하고 모든 부분을 끊어보며 진행한 뒤 최종적으로 answer_list에서 최소값을 답으로 반환하면 된다.