99클럽 코테 스터디 24일차 TIL : 프로그래머스 전력망을 둘로 나누기, 완전탐색

 

1. 오늘의 문제

 

오늘 문제는 프로그래머스의 전력망을 둘로 나누기 였다.

 

처음 문제를 접했을 때는 어떻게 풀어야 하는지 상당히 난감했다.

 

문제 설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

 

 

2. 원리

 

시각적으로 보기에는 쉽게 나눌 수 있지만, 코드 상으로 어떻게 쪼개고 세야 할지 쉽게 감이 오지 않았다.

 

결국에는 그냥 연결을 하나씩 끊어보면서, 모든 노드의 수를 세는 수 밖에 없었다.

 

모든 노드가 무조건 트리의 형태이니, 연결이 하나가  끊어지면 나머지 하나 또한 트리의 형태이다.

 

그래서 노드를 램던하게 지정해 하나의 트리를 탐색하면 나머지 트리 하나는 탐색할 필요가 없다.

 

'모든 노드의 수 - 탐색한 트리의 수 = 남은 노드의 수' 이다.

 

3. 코드

 

from collections import deque

def solution(n, wires):
    answers = []
    for wire in range(n-1):
    
    	# 연결들 중 하나씩을 제거한 리스트를 만든다.
        copyWires = wires.copy()
        copyWires.pop(wire)
        
        # 제거된 연결 리스트 안에서 노드간의 연결을 정리한다.
        visited = [0 for i in range(n+1)]
        connected = [[] for i in range(n+1)]
        for copyWire in copyWires:
            node = copyWire[0]
            con = copyWire[1]
            connected[node].append(con)
            connected[con].append(node)
            
        # que를 만들어 노드를 탐색하면서 visited를 표시한다.
        # 그리고 시작 노드를 램던하게 정한다.
        # 어차피 노드는 2개로 나뉘므로, 하나의 트리를 탐색하고 남는 것들은 모두 연결되어 있다.
        que = deque()
        startNode = 0
        for i, c in enumerate(connected):
            if c != []:
                startNode = i
                break
        que.append(startNode)
        visited[startNode] = 1
        while que:
            nextPosis = que.popleft()
            for next in connected[nextPosis]:
                if next == []:
                    continue
                if visited[next] == 1:
                    continue
                visited[next] = 1
                que.append(next)
        # 방문한 노드를 모두 세어본다.
        # 방문하지 못한 노드는 떨어져 있다.
        # 각 노드의 차를 구한 다음 최소값을 구하고 리턴한다.
        totalOne = 0
        for v in visited:
            totalOne += v
        rest = n - totalOne
        answers.append(abs(rest-totalOne))
    return min(answers)

 

4. 느낀점

 

이번 문제는 노드 탐색과 더불어 응용이 필요한 문제였다.

 

풀이 자체는 그리 어렵지 않았지만 방법을 생각하기 까지 상당한 시간을 소모해야 했다.

 

그래서 재밌는 문제였다.