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

---

1. 전체 코드

from collections import defaultdict
def solution(n, wires):
    def dfs(x, visited):
        visited.append(x)
        for v in d[x]:
            if v not in visited:
                dfs(v, visited)

    answer = 9999999
    for i in range(len(wires)):
        temp = wires[:]
        x, y = temp[i]
        del temp[i]
        d = defaultdict(list)
        for i, j in temp:
            d[i].append(j)
            d[j].append(i)

        visited1 = []
        visited2 = []
        dfs(x, visited1)
        dfs(y, visited2)
        answer = min(answer, abs(len(visited1) - len(visited2)))
    return answer

w = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
print(solution(9, w))

---

2. 풀이

wires에 담긴 원소들을 한 개씩 제외해가면서 답을 찾아낸다. 예를들어 [4, 7]을 제외할 경우 송전탑들의 연결 상태는 [[1,3],[2,3],[3,4],[4,5],[4,6],[7,8],[7,9]]이다.

그 후, 제외한 4와 7을 시작점으로 하는 DFS(4)와 DFS(7)을 통해 각각 방문한 송전탑을 담고있는 리스트인 visited1과 visited2를 구한다. 두 리스트의 길이를 구하여 차의 절대값을 구하면 두 전력망이 가지고 있는 송전탑 개수의 차이를 얻을 수 있다. 마지막으로 min을 통해 최솟값을 계속하여 최신화하면 답이 나오게 된다.