프로그래머스 Lv2 전력망을 둘로 나누기 (python)

전력망을 둘로 나누기

 

 

풀이

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

처음에는 일단 행렬을 만들고 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