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

전력망을 둘로 나누기

dfs 풀이

def solution(n, wires):
    
    #dfs로 풀기
    
    graph = [[] for _ in range(n+1)]
    for x, y in wires:
        graph[x].append(y)
        graph[y].append(x)

    
    def dfs(x, y, visit, graph):
        # x에만 연결된 그래프. y는 연결되지 않은
        nonlocal cnt
        
        visit.add(x)
        cnt += 1
        
        for ad in graph[x]:
            if ad not in visit and ad != y:
                dfs(ad, y, visit, graph)
                
        return cnt
        
    
    
    # x, y 끊는다.
    min_diff = n
    for x, y in wires:
        visit = set()
        cnt = 0
        result = dfs(x, y, visit, graph)
        diff = abs(n-2*result)
        min_diff = min(min_diff, diff)
        
    return min_diff
        

bfs 풀이

from collections import deque

def solution(n, wires):
    
    #bfs로 풀기
    
    graph = [[] for _ in range(n+1)]
    for x, y in wires:
        graph[x].append(y)
        graph[y].append(x)

    
    def bfs(x, y, visit, graph):
        nonlocal cnt
        
        visit.add(x)
        queue = deque([x])
        cnt += 1
        
        while queue:
            x = queue.popleft()
            
            for ad in graph[x]:
                if ad not in visit and ad != y:
                    visit.add(ad)
                    queue.append(ad)
                    cnt += 1
                    
        return cnt
    
    
    # x, y 끊는다.
    min_diff = n
    for x, y in wires:
        visit = set()
        cnt = 0
        result = bfs(x, y, visit, graph)
        diff = abs(n-2*result)
        min_diff = min(min_diff, diff)
        
    return min_diff
        

union-find 풀이