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

1. 문제 설명 및 분석

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

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

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

n범위를 생각했을 때 완전 탐색을 해도 무리가 없음을 실전 테스트에서도 추측할 필요가 있음.

입출력 예

n	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1

2. 문제 해결

사고 과정

• 전선을 하나씩 제거해 보며 나올 수 있는 경우의 수 탐색
• 트리의 특성상 하나의 전선을 제거하면 반드시 두 개의 무리로 나뉘게 될 것.
• 즉, 전선에 연결된 두 개의 송전탑(예: 전선이 [1, 2]일 때 송전탑은 1, 2)을 집합에 포함.
• 그리고 집합에 포함된 송전탑과 연결된 모든 전선(예: [2, 3])의 송전탑을 포함하면 한 무리가 생김.
• 모든 경우의 2 * 한 무리 송전탑의 수 - 모든 송전탑의 수의 절대값 중에서 가장 작은 값이 정답.

코드 작성

def solution(n, wires):
    answer = []

    if n == 2: # 송전탑의 수가 2개일 경우 아래의 루프에서 오류가 발생하므로 예외적으로 처리
        return 0

    for i in range(len(wires)):
        group = set()
        for x in range(len(wires)):
            if x == i:
                continue
            if not group: # 집합이 비었을 경우에 송전탑 산입
                group.update(wires[x])
            elif wires[x][0] in group or wires[x][1] in group: # 기존 집합의 송전탑과 연결이 되는 전선인 경우
                group.update(wires[x])
        answer.append(abs(n - 2 * len(group)))

    return min(answer)

제출 결과

3. 실패 분석 및 문제 해결

실패 분석

• 모든 송전탑의 연결 관계를 탐색하지 못하는 경우가 있다. → 집합으로 그룹화 하는 과정에서 연결 관계가 없는 전선이라고 판단하고 지나쳤으나 이후의 전선에서 연결 관계가 생기는 경우를 예상한다.
• 즉, 지나친 전선도 한번 더 탐색할 수있도록 구현할 필요가 있다.

코드 작성

def search_handler(remain, group):
    if not remain: # 탐색할 전선이 없을 때 탐색 종료
        return

    new_remain = [] # 지나친 전선을 기억해두어 재탐색 할 수 있도록 함
    for i in remain:
        if set(i) & group: # ? 교집합을 찾는 연산자
            group.update(i)
        else:
            new_remain.append(i)

    if len(remain) == len(new_remain): # 전선을 모두 탐색을 했을 때 전선 수의 변화가 없다면 탐색 종료
        return

    return search_handler(new_remain, group)


def solution(n, wires):
    answer = []

    if n == 2:
        return 0

    for i in range(len(wires)):
        removed = [wires[x] for x in range(len(wires)) if x != i]
        group = set(removed.pop())

        search_handler(removed, group) # 모든 전선을 빠짐없이 탐색

        answer.append(abs(n - 2 * len(group)))

    return min(answer)

제출 결과

4. 회고

• 프로그래머스 카테고리를 봤을 때 BFS 또는 DFS를 이용한 완전탐색으로 문제를 해결하도록 의도한 것인데, 운 좋게 풀어버린 것 같다.
• 실전에선 출제 의도를 정확히 파악할 필요가 있을 것 같다.
• 참고로 챗GPT에게 BFS를 이용한 완전탐색 해결법은 아래와 같다.

from collections import deque


def bfs_count(graph, start, visited):
    queue = deque([start])
    count = 0 # 한 무리의 송전탑 수
    while queue:
        node = queue.popleft()
        # 아직 방문하지 않은 송전탑이라면 방문함으로 처리하며, 한 무리에 송전탑 추가
        if not visited[node]:
            visited[node] = True
            count += 1
            # 송전탑과 연결된 모든 송전탑을 탐색 후, 방문한 적이 없으면 다음 탐색 기준 노드로 사용
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    queue.append(neighbor)
    return count


def solution(n, wires):
    answer = n

    for i in range(len(wires)):
        # 각 송전탑의 연결관계 그래프 생성
        graph = {i: [] for i in range(1, n + 1)}
        for j in range(len(wires)):
            if i == j:
                continue
            a, b = wires[j]
            graph[a].append(b)
            graph[b].append(a)

        # 한 쪽 무리의 크기 계산 (시작점은 임의의 노드)
        visited = [False] * (n + 1)
        count = bfs_count(graph, 1, visited)

        diff = abs((n - count) - count) # 두 트리의 차이 계산
        answer = min(answer, diff)

    return answer