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

문제 설명

트리 형태로 연결된 송전탑의 개수와 연결 정보가 주어지고, 전선 하나를 끊어 두 전력망의 송전탑 개수가 최대한 비슷하도록 만들 때 두 전력망의 송전탑 개수의 차이를 구하는 문제

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

프로그래머스

• 알고리즘 분류 - 완전탐색 (Brute Force)
• 난이도 - Level2

---

관련 개념

그래프 탐색?

---

접근 방법

DFS로 하나의 전력망을 탐색하여 방문한 송전탑의 개수를 구하고, 방문하지 않은 송전탑의 개수와의 차이를 구했다.

+) DFS를 편하게 구현하기 위해 전선 정보들을 인접리스트 형태의 그래프로 변환했다.

---

답안 코드

from collections import deque

def edges2list(n, edges):
    graph = {}
    
    for i in range(len(edges)):
        n1, n2 = edges[i]
        if n1 not in graph:
            graph[n1] = [n2]
        elif n2 not in graph[n1]:
            graph[n1].append(n2)
            
        if n2 not in graph:
            graph[n2] = [n1]
        elif n1 not in graph[n2]:
            graph[n2].append(n1)
    
    return graph

def dfs(graph, start):
    visited = []
    stack = deque([start])
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.append(node)
            stack.extend(graph[node]) #####
    
    return visited
    
def solution(n, wires):
    answer = n
    
    # 앞에서부터 전선 빼보기
    for i in range(len(wires)):
        tmp = wires[:]
        del(tmp[i])
        
        graph = edges2list(n, tmp)
        v = dfs(graph, tmp[0][0])

        if abs(n-len(v)-len(v)) < answer:
            answer = abs(n-len(v)-len(v))

    return answer

DFS 없이 풀고 싶었는데 도저히 생각이 안 나서 실패....