완전탐색 - 전력망을 둘로 나누기

 

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

프로그래머스

 

이 문제는, 송전탑들이 연결되어 있는 모습이 트리 형태이고 예시 그림처럼 생각해볼 수 있기 때문에

완전탐색 문제이지만 dfs 혹은 bfs 알고리즘을 함께 활용하면 쉽게 풀 수 있다.

 

import copy

def dfs(graph, start, visited):
    visited[start] = True
    for i in graph[start]:
        if not visited[i]:
            dfs(graph, i, visited)
    return visited


def solution(n , wires):
    answer = n - 2

    for i in range(len(wires)):
        new_wires = copy.deepcopy(wires)
        new_wires.pop(i)
        # dfs를 위한 그래프와 visited 리스트 만들기
        graph = [[] for i in range(n+1)]
        visited = [False] * (n+1)

        for wire in new_wires:
            graph[wire[0]].append(wire[1])
            graph[wire[1]].append(wire[0])
    
        for i, g in enumerate(graph):
            if g:
                start = i
                break
        count = dfs(graph, start, visited).count(True)
        diff = abs(count - (n - count))

        answer = min(answer, diff)

    return answer

우선 copy 모듈을 import 한 이유는, 파이썬에서 리스트는 변수에 할당 될때 call by reference 방식으로 할당 되기 때문에,

기존의 wires를 그냥 new_wires = wires 로 할당 했을때, new_wires에 생긴 변경사항이 기존의 wires에도 반영이 된다.

완전탐색을 위해 wires에서 연결망을 하나씩 끊어봐야 하는데, 그 변경사항이 기존의 wires에는 반영이 되지 않게 하기 위해

copy 모듈의 deepcopy를 이용해 new_wires를 생성해준 것이다.

 

다음으로 보이는 dfs 함수는 연결된 노드들(송전탑들)을 체크하기 위해 필요하다.

solution 함수로 넘어가면 제일 먼저 answer 변수를 볼 수 있는데, answer 변수의 초기값은 전력망을 두개로 나눴을 때 송전탑의 개수 차이가 가장 큰 경우를 초기값으로 설정한다. 

차이가 가장 크려면 한 개의 송전탑만 분리되었을 경우이고, 이 경우 두 전력망의 송전탑 개수 차이는 (n - 1) - 1 = n - 2 이다.

 

그 다음 for 문은 wires의 개수만큼 반복이 이루어지고, 완전탐색을 위해 각 전선들을 하나씩 끊어보고 그때마다 두 전력망의 송전탑 개수 차이를 비교해서 매번 작은 값으로 answer를 갱신해준다.

가장 바깥 for문 안에서 전선을 제거했을 때의 송전탑들의 연결 모습을 graph로 만들어주는 과정이 내부의 첫 for문이다.

 

그리고 내부의 두 번째 for문은 다른 송전탑과 연결된 송전탑을 찾기 위한 과정인데, graph를 돌면서 다른 송전탑과 연결되어있는 송전탑을 찾으면 바로 반복을 멈추고 그 송전탑부터 dfs를 시작하는 것이다.

 

dfs를 통해 연결된 송전탑들의 값이 visited 리스트에서 True로 바뀌는데, 연결된 송전탑들을 다 탐색하면 dfs 함수의 재귀 실행이 멈출 것이고 이 때 dfs 함수는 visited 리스트를 반환한다.

그럼 visited에서 True의 개수가 나눠진 두 전력망 중, 한쪽 전력망에서의 송전탑 개수이다. 

그럼 나머지 전력망의 송전탑 개수는 n - count 이기 때문에, 이 둘의 차의 절대값인 diff 를 현재 answer와 비교해서 더 작은 값을 

answer에 담으면 된다.