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

사용 언어 - Python3

문제 - 전력망을 둘로 나누기

프로그래머스

 

 

정답

완전탐색 BFS 문제 (정답 맞춘 여부 X)

정답 풀이

해당 와이어를 끊었을 때, BFS를 돌려서 한쪽 영역의 노드 수를 구한다.

BFS) 해당 노드를 방문하지 않은 경우, 연결된 노드수 result를 구한다.

앞서 저장된 answer값과 현재 result로 구한 노드 간의 차를 비교했을 때, 더 작은 값으로 return 한다.

# 정답
from collections import deque

def bfs(start,visited,graph):
    queue = deque([start])
    result = 1 #연결된 노드수
    visited[start] = True #시작 노드 방문 처리
    while queue: #bfs 수행
        now = queue.popleft()
        
        for i in graph[now]: #now 노드와 연결된 노드에 대해서
            if visited[i] == False: #방문하지 않았을 경우만
                result += 1
                queue.append(i)
                visited[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:
        visited = [False]*(n+1)
        visited[not_visit] = True
        # 해당 노드 끊었을 때, 한쪽 영역의 노드 수 result 구하기
        result = bfs(start,visited,graph)
        # 기존 answer보다 현재구한 값이 더 작으면 최소값 업데이트
        if abs(result - (n-result)) < answer:
            answer = abs(result - (n-result))
        
    return answer

 

 

 

---

레퍼런스

• 정답 참고

프로그래머스 : 전력망을 둘로 나누기

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부