[프로그래머스] 전력망 두 개로 나누기

문제 설명

문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

 

풀이

>> BFS

from collections import deque

def make_graph(wires, n):
    cnt = 0
    graph = []

    for i in range(n + 1):
        node = []
        graph.append(node)

    for i in range(len(wires)):
        graph[wires[i][0]].append(wires[i][1])
        graph[wires[i][1]].append(wires[i][0])

    return graph

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    list = []

    while queue:
        v = queue.popleft()
        list.append(v)

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

    return list

def solution(n, wires):
    answer = 100
    wires = sorted(wires, key = lambda x : (x[0], x[1]))

    for i in range(len(wires)):
        wire = wires[:i]+wires[i+1:]

        graph = make_graph(wire, n)

        node = []
        node = set(node)
        for j in range(1, n + 1):
            visited = [False] * (n + 1)
            bfs(graph, j, visited)
            node.add(visited.count(True))

        if max(node) - min(node) < answer:
            answer = max(node) - min(node)

    return answer

 

 

>>DFS

def dfs(v, graph, visited):
    visited[v] = True
    return sum([1] + [dfs(u, graph, visited) for u in graph[v] if not visited[u]])

def solution(n, wires):
    graph = [[] for _ in range(n+1)]
    for v, u in wires:
        graph[v].append(u)
        graph[u].append(v)

    answer = 100
    for i in range(n-1):
        visited = [False for _ in range(n+1)]
        v1, v2 = wires[i]
        visited[v2] = True
        tmp = abs(dfs(v1, graph, visited) - dfs(v2, graph, visited))
        answer = min(tmp, answer)

    return answer

 

만약 첫 번째 [1,3]이 끊어진다면, 1과 3에서 시작한 노드 경로는 독립일 것이다.

그래서 1에서 시작을 할 때, 3은 방문하지 않을 것이므로 미리 visitied[v2] = True 를 선언한다. 

 

출처

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

프로그래머스