전력망을 둘로 나누기

풀이

사실 어떻게 풀어야하는지 도저히 감이 안와서 결국 남의 힘을 빌렸다.

처음에는 일단 행렬을 만들고 dfs나 bfs로 풀어야한다는 것은 알았지만, 구현을 어떻게 해야하는지 답이 안나와서 힘을 빌려 아래처럼 제출했다.

def solution(n, wires):
    # 각 송전탑을 연결하는 인접 리스트 생성
    graph = [[] for _ in range(n+1)]
    for a, b in wires:
        graph[a].append(b)
        graph[b].append(a)

    # 각 송전탑에 연결된 예하 송전탑의 노드 수를 계산
    count = [0] * (n+1)
    def dfs(node, parent):
        for child in graph[node]:
            if child != parent:
                dfs(child, node)
                count[node] += count[child]
        count[node] += 1

    dfs(1, 0)

    # 전선하나 제거 시, 두 노드 수 차이를 계산
    answer = n
    for a, b in wires:
        answer = min(answer, abs(n - 2*count[a]), abs(n - 2*count[b]))

    return answer

다른 사람 풀이

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