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
https://hwayomingdlog.tistory.com/300
'⌨️ Algorithms > 프로그래머스' 카테고리의 다른 글
[Python] 프로그래머스 Lv1_삼총사 (0) | 2023.01.13 |
---|---|
[Python] 프로그래머스 Lv2_카펫 (0) | 2023.01.12 |
[Python] 프로그래머스 Lv1_핸드폰 번호 가리기 (0) | 2023.01.10 |
[Python] 프로그래머스 Lv1_행렬의 덧셈 (1) | 2023.01.10 |
[Python] 프로그래머스 Lv3_거스름돈 (0) | 2023.01.10 |
Contents
소중한 공감 감사합니다 :)