[PG] 전력망을 둘로 나누기

문제

me

from collections import deque, defaultdict

def bfs(start, nomore, n, route_):
    q = deque([start])
    visit = [False] * (n + 1)
    visit[start] = True
    visit[nomore] = True  # 연결 제외
    length = 1
    while q:
        front = q.popleft()
        for next in route_[front]:
            if not visit[next]:
                q.append(next)
                visit[next]=True
                length += 1
    return length

def solution(n, wires):
    route_ = defaultdict(list)
    for a, b in wires:
        route_[a].append(b)
        route_[b].append(a)
    small_gap = 101
    for i, [a, b] in enumerate(wires):
        small_gap = min(small_gap, abs(bfs(a, b, n, route_) - bfs(b, a, n, route_)))
    return small_gap

• bfs 사용

others

uf = []

def find(a):
    global uf
    if uf[a] < 0: return a # -1이라면 자기 자신 반환
    uf[a] = find(uf[a]) # 아니라면 내 부모의 부모를 찾아 나서기
    return uf[a]

def merge(a, b):
    global uf
    pa = find(a)
    pb = find(b)
    if pa == pb: return
    uf[pa] += uf[pb] # a에 b 연결해주기
    uf[pb] = pa # b의 부모가 a가 됨

def solution(n, wires):
    global uf
    answer = int(1e9)
    k = len(wires)
    for i in range(k):
        uf = [-1 for _ in range(n+1)] # 매번 uf를 위해 부모 갱신
        tmp = [wires[x] for x in range(k) if x != i] # 순서대로 연결 끊기
        for a, b in tmp: merge(a, b) # 관계 연결하기
        v = [x for x in uf[1:] if x < 0] # ?????
        answer = min(answer, abs(v[0]-v[1]))

    return answer

• kruskal 이용