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

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

프로그래머스

 

• n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있음
• 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 함
• 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 함
• n: 송전탑의 개수
• wires: 전선 정보
• 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return

제한사항

• n은 2 이상 100 이하인 자연수
• wires는 길이가 n-1인 정수형 2차원 배열
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미
  • 1 ≤ v1 < v2 ≤ n
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않음

 

"""
입출력 예시)

n = 9, wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] -> 3
n = 4, wires = [[1,2],[2,3],[3,4]] -> 0
n = 7, wires = [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] -> 1
"""

 

• n = 9, wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] -> 3

 

-> 4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없음

-> 3번과 4번을 연결하는 전선을 끊어도 최선의 정답 도출 가능

 

 

• n = 4, wires = [[1,2],[2,3],[3,4]] -> 0

-> 2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선

 

 

• n = 7, wires = [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] -> 1

-> 3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선

 

 

## 의사코드 ##


# 트리 -> BFS
# -> deque로 BFS 구현

# graph -> defaultdict(list)


# 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return
# -> abs()

 

 

 

통과한 코드

 

from collections import deque, defaultdict

def bfs(graph, start, visited):
    # 시작 노드를 큐에 삽입
    q = deque([start])
    # 시작 노드 방문처리 
    visited[start] = True
    # 시작 노드와 연결되어 있는 노드의 수
    connected_n = 1

    while q:
        # 현재 노드 = 큐의 맨 앞 원소
        v = q.popleft()
        # 현재 노드(v)와 연결되어 있는 노드 중 방문하지 않은 노드 탐색
        for i in graph[v]:
            if not visited[i]:
                q.append(i) # 큐에 i 삽입
                visited[i] = True # i 방문처리
                # 새로운 노드를 탐색했으니 연결되어 있는 노드 수 + 1
                connected_n += 1 
    return connected_n # 시작 노드와 연결되어 있는 노드의 수를 반환


def solution(n, wires):
    answer = n
    wires_q = deque(wires) # wires를 deque로 변환
    
    for _ in range(len(wires)):
        # wires_q의 맨 앞의 전선 끊기
        broken_wire = wires_q.popleft()
        # visited 초기화 
        visited = [0] * (n+1)
        # 두 전력망이 가지고 있는 송전탑의 개수
        tower_n = []
        graph = defaultdict(list)
        # graph에 값 삽입
        for v1, v2 in wires_q:
            graph[v1].append(v2)
            graph[v2].append(v1)
            
        # graph 탐색
        for i in range(1, n+1):
            # i가 방문하지 않은 노드이면 해당 노드를 시작 노드로 graph 탐색 
            if not visited[i]:
                tower_n.append(bfs(graph, i, visited))
                
        # 두 전력망의 송전탑 개수 차이보다 answer가 더 크면 answer 값을 갱신 
        answer = min(abs(tower_n[0] - tower_n[1]), answer)
        # 끊었던 전선을 다시 wires_q에 삽입해서 붙이기
        wires_q.append(broken_wire)
        
    return answer

 

 

• 과정 확인

# n = 7
# wires = [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]

"""
원래의 wires_q: deque([[1, 2], [2, 7], [3, 7], [3, 4], [4, 5], [6, 7]])
broken_wire: [1, 2]
graph: defaultdict(<class 'list'>, {2: [7], 7: [2, 3, 6], 3: [7, 4], 4: [3, 5], 5: [4], 6: [7]}) 

bfs의 graph: defaultdict(<class 'list'>, {2: [7], 7: [2, 3, 6], 3: [7, 4], 4: [3, 5], 5: [4], 6: [7], 1: []})
bfs의 start: 1
bfs의 visited: [0, True, 0, 0, 0, 0, 0, 0]
connected_n: 1 

bfs의 graph: defaultdict(<class 'list'>, {2: [7], 7: [2, 3, 6], 3: [7, 4], 4: [3, 5], 5: [4], 6: [7], 1: []})
bfs의 start: 2
bfs의 visited: [0, True, True, True, True, True, True, True]
connected_n: 6 

tower_n: [1, 6]
갱신된 answer: 5
끊었던 전선을 다시 붙인 wires_q: deque([[2, 7], [3, 7], [3, 4], [4, 5], [6, 7], [1, 2]]) 

--------------------------------------------------------------------------------
broken_wire: [2, 7]
graph: defaultdict(<class 'list'>, {3: [7, 4], 7: [3, 6], 4: [3, 5], 5: [4], 6: [7], 1: [2], 2: [1]}) 

bfs의 graph: defaultdict(<class 'list'>, {3: [7, 4], 7: [3, 6], 4: [3, 5], 5: [4], 6: [7], 1: [2], 2: [1]})
bfs의 start: 1
bfs의 visited: [0, True, True, 0, 0, 0, 0, 0]
connected_n: 2 

bfs의 graph: defaultdict(<class 'list'>, {3: [7, 4], 7: [3, 6], 4: [3, 5], 5: [4], 6: [7], 1: [2], 2: [1]})
bfs의 start: 3
bfs의 visited: [0, True, True, True, True, True, True, True]
connected_n: 5 

tower_n: [2, 5]
갱신된 answer: 3
끊었던 전선을 다시 붙인 wires_q: deque([[3, 7], [3, 4], [4, 5], [6, 7], [1, 2], [2, 7]]) 

--------------------------------------------------------------------------------
broken_wire: [3, 7]
graph: defaultdict(<class 'list'>, {3: [4], 4: [3, 5], 5: [4], 6: [7], 7: [6, 2], 1: [2], 2: [1, 7]}) 

bfs의 graph: defaultdict(<class 'list'>, {3: [4], 4: [3, 5], 5: [4], 6: [7], 7: [6, 2], 1: [2], 2: [1, 7]})
bfs의 start: 1
bfs의 visited: [0, True, True, 0, 0, 0, True, True]
connected_n: 4 

bfs의 graph: defaultdict(<class 'list'>, {3: [4], 4: [3, 5], 5: [4], 6: [7], 7: [6, 2], 1: [2], 2: [1, 7]})
bfs의 start: 3
bfs의 visited: [0, True, True, True, True, True, True, True]
connected_n: 3 

tower_n: [4, 3]
갱신된 answer: 1
끊었던 전선을 다시 붙인 wires_q: deque([[3, 4], [4, 5], [6, 7], [1, 2], [2, 7], [3, 7]]) 

--------------------------------------------------------------------------------
broken_wire: [3, 4]
graph: defaultdict(<class 'list'>, {4: [5], 5: [4], 6: [7], 7: [6, 2, 3], 1: [2], 2: [1, 7], 3: [7]}) 

bfs의 graph: defaultdict(<class 'list'>, {4: [5], 5: [4], 6: [7], 7: [6, 2, 3], 1: [2], 2: [1, 7], 3: [7]})
bfs의 start: 1
bfs의 visited: [0, True, True, True, 0, 0, True, True]
connected_n: 5 

bfs의 graph: defaultdict(<class 'list'>, {4: [5], 5: [4], 6: [7], 7: [6, 2, 3], 1: [2], 2: [1, 7], 3: [7]})
bfs의 start: 4
bfs의 visited: [0, True, True, True, True, True, True, True]
connected_n: 2 

tower_n: [5, 2]
갱신된 answer: 1
끊었던 전선을 다시 붙인 wires_q: deque([[4, 5], [6, 7], [1, 2], [2, 7], [3, 7], [3, 4]]) 

--------------------------------------------------------------------------------
broken_wire: [4, 5]
graph: defaultdict(<class 'list'>, {6: [7], 7: [6, 2, 3], 1: [2], 2: [1, 7], 3: [7, 4], 4: [3]}) 

bfs의 graph: defaultdict(<class 'list'>, {6: [7], 7: [6, 2, 3], 1: [2], 2: [1, 7], 3: [7, 4], 4: [3]})
bfs의 start: 1
bfs의 visited: [0, True, True, True, True, 0, True, True]
connected_n: 6 

bfs의 graph: defaultdict(<class 'list'>, {6: [7], 7: [6, 2, 3], 1: [2], 2: [1, 7], 3: [7, 4], 4: [3], 5: []})
bfs의 start: 5
bfs의 visited: [0, True, True, True, True, True, True, True]
connected_n: 1 

tower_n: [6, 1]
갱신된 answer: 1
끊었던 전선을 다시 붙인 wires_q: deque([[6, 7], [1, 2], [2, 7], [3, 7], [3, 4], [4, 5]]) 

--------------------------------------------------------------------------------
broken_wire: [6, 7]
graph: defaultdict(<class 'list'>, {1: [2], 2: [1, 7], 7: [2, 3], 3: [7, 4], 4: [3, 5], 5: [4]}) 

bfs의 graph: defaultdict(<class 'list'>, {1: [2], 2: [1, 7], 7: [2, 3], 3: [7, 4], 4: [3, 5], 5: [4]})
bfs의 start: 1
bfs의 visited: [0, True, True, True, True, True, 0, True]
connected_n: 6 

bfs의 graph: defaultdict(<class 'list'>, {1: [2], 2: [1, 7], 7: [2, 3], 3: [7, 4], 4: [3, 5], 5: [4], 6: []})
bfs의 start: 6
bfs의 visited: [0, True, True, True, True, True, True, True]
connected_n: 1 

tower_n: [6, 1]
갱신된 answer: 1
끊었던 전선을 다시 붙인 wires_q: deque([[1, 2], [2, 7], [3, 7], [3, 4], [4, 5], [6, 7]]) 

--------------------------------------------------------------------------------
1
"""

 

 

 

참고) 

 

https://heytech.tistory.com/56

[Python] BFS 알고리즘 개념 및 실습

 

https://hwayomingdlog.tistory.com/300

Level 2 전력망을 둘로 나누기 Python 3