프로그래머스: [전력망을 둘로 나누기]

📌 프로그래머스: [전력망을 둘로 나누기]

🔗 문제 링크

---

문제 설명 📄

하나의 전력망으로 연결된 n개의 송전탑이 있다.
wires 리스트는 송전탑을 연결하는 전선 정보를 제공한다.
전선 하나를 끊어 두 개의 네트워크로 분리할 때, 두 네트워크의 송전탑 개수 차이를 최소화해야 한다.

---

문제 접근 방식 💡

• 모든 전선을 하나씩 제거한 후, 남은 네트워크에서 DFS를 사용하여 연결된 송전탑 개수를 계산.
• 하나의 네트워크 크기를 구하면, 나머지 네트워크의 개수는 전체 개수에서 빼면 됨.
• 가장 작은 차이를 찾도록 갱신.

---

Solution 💻

from collections import defaultdict

def search(index, visit, graph):
    count = 1
    for i in graph[index]:
        if i not in visit:
            visit.add(i)
            count += search(i, visit, graph)
    return count

def solution(n, wires):
    answer = float('inf')
    graph = defaultdict(list)
    
    for s, e in wires:
        graph[s].append(e)
        graph[e].append(s)
    
    for s, e in wires:
        graph[s].remove(e)
        graph[e].remove(s)
        
        visited = set()
        visited.add(s)
        one = search(s, visited, graph)
        
        two = n - one
        answer = min(answer, abs(one - two))
        
        graph[s].append(e)
        graph[e].append(s)
    
    return answer

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(N^2),
  • N개의 간선을 하나씩 제거하면서 O(N) DFS 탐색 수행.
• 공간 복잡도: O(N),
  • 그래프를 저장하는 defaultdict 및 방문 기록을 위한 set 사용.