[프로그래머스] 전력망을 둘로 나누기 (Python, BFS, 완전탐색)

 

 

🌱 문제

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

프로그래머스

 

 

 

🌱 풀이

n은 2 이상 100 이하인 자연수이고 wires는 길이가 n-1인 2차원 배열로, 시간복잡도가 $O({100}^2)$을 넘지 않으므로 (n-1 배열 탐색($O(N)$) * BFS 시간복잡도($O(N)$)) 완전 탐색을 이용해서 풀이합니다.

1. 전력망(graph) 정보를 2차원 리스트 형태로 표현하기

  

    
    
    
    
  
graph = [[] for _ in range(n + 1)]
for wire in wires:
    graph[wire[0]].append(wire[1])
    graph[wire[1]].append(wire[0])

 

2. 전력망을 하나씩 끊어보기 - 모든 경우 탐색(완전 탐색)

wires를 반복문으로 돌면서 전력망을 하나씩 끊어봅니다. 이때, graph 정보를 deepcopy해서 연결된 노드 정보를 제거하여도 원래 graph 정보에는 변화가 없도록 합니다.

  

    
    
    
    
  
for wire in wires:
    graph_ = deepcopy(graph)
    graph_[wire[0]].remove(wire[1])
    graph_[wire[1]].remove(wire[0])

 

3. 각 전력망에 있는 송전탑의 개수 세기

전력망을 끊으면 하나의 전력망이 둘로 쪼개집니다. 우리는 둘로 쪼개어진 각 전력망(그래프)에서 송전탑(노드)이 몇 개 있는지 카운트 한 후, 그 차이를 구하면 됩니다. 이때 연결된 노드의 개수는 DFS나 BFS로 셀 수 있는데, 저는 BFS로 구해보겠습니다.

  

    
    
    
    
  
def bfs(graph, start):
    count = 1
    queue = deque([start])
    visited = [False] * (len(graph) + 1)
    visited[start] = True

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

        count += 1

    return count

BFS에 들어가는 시작노드는 끊은 wire의 두 개의 노드를 시작노드로 하면 됩니다.

  

    
    
    
    
  
count1, count2 = bfs(graph_, wire[0]), bfs(graph_, wire[1])

 

 

 

🌱 정답 코드 

  

    
    
    
    
  
# !/usr/bin/env python
# -*- coding: utf-8 -*-
# programmers 전력망을 둘로 나누기

from collections import deque
from copy import deepcopy


# 하나의 전력망에 몇 개의 송전탑이 있는지 세기
def bfs(graph, start):
    count = 1
    queue = deque([start])
    visited = [False] * (len(graph) + 1)
    visited[start] = True

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

        count += 1

    return count


def solution(n, wires):
    answer = 100

    graph = [[] for _ in range(n + 1)]
    for wire in wires:
        graph[wire[0]].append(wire[1])
        graph[wire[1]].append(wire[0])

    for wire in wires:
        graph_ = deepcopy(graph)
        graph_[wire[0]].remove(wire[1])
        graph_[wire[1]].remove(wire[0])

        count1, count2 = bfs(graph_, wire[0]), bfs(graph_, wire[1])

        res = abs(count1 - count2)
        if res < answer:
            answer = res

    return answer