프로그래머스 Lv2 | 완전탐색 | 전력망을 둘로 나누기

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

프로그래머스

 

2026.04.01

잘린거 고려하는걸 그냥 cut_a, cut_b로 하면 간단했음

def dfs(curr, graph, visited, cut_a, cut_b):
    visited[curr] = True
    cnt = 1
    
    for g in graph[curr]:
        if (curr == cut_a and g == cut_b) or (curr == cut_b and g == cut_a):
            continue
        if not visited[g]:
            cnt += dfs(g, graph, visited, cut_a, cut_b)
    return cnt

def solution(n, wires):
    graph = [[] for _ in range(n+1)]
    for w in wires:
        a, b = w
        graph[a].append(b); graph[b].append(a)
        
    diff = []
    for w in wires:
        cut_a, cut_b = w
        visited = [False] * (n+1)
        cut1 = dfs(cut_a, graph, visited, cut_a, cut_b)
        cut2 = n - cut1
        diff.append(abs(cut1-cut2))
    
    return min(diff)

 

---

연결된 개수 셀 때, 전역변수를 사용하지 않는다면 cnt += dfs를 사용할 것

그래프 만들어서 접근하는건 잘했음

def dfs(wires, graph, curr, no_wire_idx, visited):
    cnt = 1
    visited[curr] = True
    for next in graph[curr]:
        if not visited[next]:
            if curr and next not in wires[no_wire_idx]:
                cnt += dfs(wires, graph, next, no_wire_idx, visited)
    return cnt

def solution(n, wires):    
    # graph 만들기
    graph = [[] for _ in range(n+1)]
    for i in range(len(wires)):
        a, b = wires[i]
        graph[a].append(b); graph[b].append(a)
    
    result_list = set()
    # 모든 전선에 대하여 한번씩 진행
    for i in range(len(wires)):
        a, b = wires[i]
        visited = [False] * (n+1)
        group1 = dfs(wires, graph, a, i, visited)
        group2 = n - group1
        result_list.add(group1-group2 if group1>group2 else group2-group1)
    
    return min(result_list)