프로그래머스 - 전력망을 둘로 나누기 / Level 2 / Python

문제 📋

프로그래머스 - 전력망을 둘로 나누기

풀이 📝

from collections import defaultdict


def dfs(cur, cnt):
    global visited
    visited[cur] = True
    cnt += 1
    
    for node in graph[cur]:
        if not visited[node] and is_connect[cur][node]:
            cnt = dfs(node, cnt)
    return cnt


def solution(n, wires):
    answer = int(1e9)
    
    global visited
    global graph
    global is_connect
    
    graph = defaultdict(list)
    is_connect = [[False] * (n+1) for _ in range(n+1)]
    
    for start, end in wires:
        graph[start].append(end)
        graph[end].append(start)
        is_connect[start][end] = True
        is_connect[end][start] = True
    
    for start, end in wires:
        visited = [False] * (n+1)
        
        is_connect[start][end] = False
        is_connect[end][start] = False
        
        result = abs(dfs(start, 0) - dfs(end, 0))
        
        if answer > result:
            answer = result
        
        is_connect[start][end] = True
        is_connect[end][start] = True
    
    return answer

1. 문제 정의
   하나의 트리를 둘로 나눈 뒤 노드의 개수의 차가 최소가 되도록 하는 문제이다.

2. 시간 복잡도 계산
   완전 탐색이 먼저 가능한지 계산해 봤다.
   n이 최대 100이므로 최대 99개의 edge 중 하나를 선택하는 경우의 수는 99이고
   그때마다 최대 100개의 노드를 탐색한다면 최대 연산 횟수는 9900이다.
   따라서 완전 탐색이 충분히 가능하다.

3. 문제 풀이
   연결정보를 하나씩 제거해 보고 제거 지점에서 각각의 트리에 대하여
   DFS로 한 번씩 순회하여 노드 수의 차를 계산해 주었다.

4. 예외 사항
   문제 조건에 따라 기타 예외 사항은 발생하지 않음 확인.