86971. 전력망을 둘로 나누기

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

프로그래머스

def solution(n, wires): # 송전탑의 개수 n, 전선 정보 wires

    def find(x,parent):     # 부모 찾기
        if parent[x] < 0:
            return x
        parent[x] = find(parent[x],parent)
        return parent[x]

    def union(x, y,parent):  # 합침
        x = find(x,parent)
        y = find(y,parent)
        if x == y:
            return -1
        if parent[x] < parent[y]:
            parent[x] += parent[y]
            parent[y] = x
        elif parent[x] > parent[y]:
            parent[y] += parent[x]
            parent[x] = y
        else:
            parent[y] += parent[x]
            parent[x] = y
        return 1

    answer = n
    for i in range(len(wires)):
        parent = [-1]*(n+1)

        for a,b in (wires[:i] + wires[i+1:]):
            union(a,b,parent)

        group1 = parent[find(wires[i][0],parent)]
        group2 = parent[find(wires[i][1],parent)]
        answer = min(answer, abs(group1-group2))
    return answer

---

실패 코드

def solution(n, wires): # 송전탑의 개수 n, 전선 정보 wires

    import copy
    min_cnt = 100000

    def find_set(x):  # 대표자 출력
        if parent[x] == x:
            return x
        parent[x] = find_set(parent[x])
        return parent[x]

    def union(x, y):  # 둘을 합침
        x = find_set(x)
        y = find_set(y)
        if x == y:
            return
        if x > y:
            parent[x] = y
        else:
            parent[y] = x

    for i in range(len(wires)):

        wires_2 = copy.deepcopy(wires)
        wires_2.pop(i)
        parent = [x for x in range(n)]

        for wire in wires_2:
            a, b = wire
            union(a-1,b-1)
        #### 첫 번째 예시에서 첫 번째 전선을 없앴을 때 parent가 [0,1,1,1,1,1,1,1,1] 이런식으로 나오는지 모를 일...
        res = set()
        for j in parent:
            if j != 0:
                res.add(j)

        if len(res) == 2:

            lst = []
            for r in res:
                lst.append(r)

            if min_cnt > abs(parent.count(lst[0])-parent.count(lst[1])):
                min_cnt = abs(parent.count(lst[0])-parent.count(lst[1]))

    return min_cnt

+ bfs 풀이

from collections import deque

def bfs(start, remove, visited, links):
    q = deque([start])
    visited[start] = 1
    cnt = 1
    while q:
        now = q.popleft()
        for nxt in links[now]:
            if not visited[nxt] and nxt != remove:
                visited[nxt] = True
                q.append(nxt)
                cnt += 1
    return cnt
    
def solution(n, wires):
    ans = float('inf')
    links = [[] for _ in range(n+1)]
    for a, b in wires: # 양방향 저장
        links[a].append(b)
        links[b].append(a)
        
    for a, b in wires:
        visited = [-1] * (n+1)
        # 하나의 간선을 제거하고 제거된 간선과 연결된 두 노드를 루트 노드로 하여 bfs를 수행
        count1 = bfs(a, b, visited, links) 
        count2 = bfs(b, a, visited, links)
        diff = abs(count1-count2)
        if diff < ans:
            ans = diff
    return ans