알고리즘
프로그래머스(programmers) 전력망을 둘로 나누기 python 정답 [완전 탐색]
TheSapper
2023. 3. 16. 00:20
반응형
프로그래머스(programmers) 전력망을 둘로 나누기 python 정답 [완전 탐색]
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/86971
문제 정답
입출력 예
n | wires | result |
9 | [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] | 3 |
4 | [[1,2],[2,3],[3,4]] | 0 |
7 | [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] | 1 |
정답 코드
from collections import deque
def bfs(start,visitied,graph):
queue = deque([start])
result = 1
visitied[start] = True
while queue:
now = queue.popleft()
for i in graph[now]:
if visitied[i] == False:
result += 1
queue.append(i)
visitied[i] = True
return result
def solution(n, wires):
answer = n
graph = [[] for _ in range(n+1)]
for v1,v2 in wires:
graph[v1].append(v2)
graph[v2].append(v1)
for start,not_visit in wires:
visitied = [False]*(n+1)
visitied[not_visit] = True
# 한 쪽만 탐색
result = bfs(start,visitied,graph)
answer = min(answer,abs(result - (n-result)))
return answer
문제 해설
이 문제는 항상 전력망이 2개로 나뉜다 가정한다.
이 경우 한쪽 전력망을 전부 방문하면 남는 전력망은 다른 전력망이 된다.
따라서 모든 노드를 시작점으로 bfs를 시도한 뒤, bfs로 연결한 노드의 수를 전체 갯수에서 빼면 다른 전력망의 노드 수가 나온다.
이 두개의 차 abs(result - (n-result))의 최솟값(min)을 갱신하면 된다.
반응형