[Level 2] / [Python] 전력망을 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

---

나의 풀이

위 그림처럼 간선이 제일 많은 노드인 #4에서 연결된 간선 중 하나를 끊고 노드 갯수를 비교하는 방법을 생각하였다.

하지만 테스트케이스 8번부터 오류를 출력하였고 반례를 찾아야만 했다.

위 그림과 같은 경우 처음에 생각했던 방식대로 진행하게 되면 #3 노드의 간선 중 하나를 끊게 되고 (3, 6)개로 나누게 된다.

하지만 정답은 #4, #5 또는 #4, #6 의 간선을 끊어 (4, 5)개로 나누어야 합니다.

따라서 for문을 하나 더 쌓아 전부 탐색하게 하였고 해결하였습니다. 다행히 시간초과는 뜨지 않았습니다.

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

    for wire in wires:
        r[wire[0]].append(wire[1])
        r[wire[1]].append(wire[0])
        
    for k in range(1, n+1):
        min_ = float('inf')
        for idx, i in enumerate(r[k]):        
            start = r[k][:idx] + r[k][idx+1:]            
            stack = [k]
            
            while start:
                i = start.pop()            
                if i not in stack:
                    stack.append(i)
                    start += r[i]
                    
            min_ = min(len(stack), min_)
        answer.append(min_)

    return abs(max(answer)-(n-max(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

set() 활용이 엄청 깔끔합니다..!