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

Python3

문제 설명

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

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

---

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ 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

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.
• 
• 4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.
• 또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.

입출력 예 #2

• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
• 
• 2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

입출력 예 #3

• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
• 
• 3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

풀이

---

Python

def solution(n, wires):
    answer = n
    graph = [[] for _ in range(n+1)]

    for wire in wires:
        graph[wire[0]].append(wire[1])
        graph[wire[1]].append(wire[0])

    for wire in wires:
        A, B = [wire[0]], [wire[1]]
        isVisit = [False] * (n+1)
        isVisit[A[0]] = True
        isVisit[B[0]] = True
        n_A, n_B = 0, 0

        while A:
            a_pop = A.pop()
            for g in graph[a_pop]:
                if not isVisit[g]:
                    A.append(g)
                    n_A += 1
                    isVisit[g] = True

        while B:
            b_pop = B.pop()
            for g in graph[b_pop]:
                if not isVisit[g]:
                    B.append(g)
                    n_B +=1
                    isVisit[g] = True

        answer = min(answer, abs(n_A - n_B))

    return answer

Python 풀이 2

def solution(n, wires):
    ans = n
    for sub in (wires[i+1:] + wires[:i] for i in range(len(wires))):
        s = set(sub[0])
        [s.update(v) for _ in sub for v in sub if set(v) & s]
        ans = min(ans, abs(2 * len(s) - n))
    return ans

설명

---

풀이 1

• A, B로 갈라진 두 그룹의 자식 노드 수를 구하는 과정을 더 간략화 할 수 있다
• 추후 다시 연습해봐야 할 좋은 문제 같다

풀이 2

• 기존 A,B로 구분하여 자식노드의 합을 구했던 방법을
• 한 엣지를 선택하고 이를 끊어 생기는 두 트리로 계산하는 방식으로 간략화
• set 자료구조를 활용하여 중복 제거
• abs( i-1-(N-i-1) ) 풀이 활용