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

https://programmers.co.kr/learn/courses/30/lessons/86971?language=python3 

코딩테스트 연습 - 전력망을 둘로 나누기

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_전력망을둘로나누기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from collections import deque, defaultdict
def bfs(start_v, graph, visit):
    q = deque([start_v])
    visit[start_v] = 1
    total = 1
    while q:
        v = q.popleft()
        for nv in graph[v]:
            if not visit[nv]:
                q.append(nv)
                visit[nv] = 1
                total += 1
    return total


def solution(n, wires):
    answer = n
    d_wires = deque(wires)
    for _ in range(len(wires)):
        broken_wire = d_wires.popleft()
        visit = [0] * (n + 1)
        tops = []
        graph = defaultdict(list)
        for v1, v2 in d_wires:
            graph[v1].append(v2)
            graph[v2].append(v1)
        for v in range(1, n + 1):
            if not visit[v]:
                tops.append(bfs(v, graph, visit))
        answer = min(abs(tops[0] - tops[1]), answer)
        d_wires.append(broken_wire)
    return answer

---

풀이 과정

풀이 시간 20분

from collections import deque, defaultdict

def bfs(start_v, graph, visit):
	#시작 노드를 큐에 담는다
    q = deque([start_v])
    
    #시작 노드를 방문처리 한다
    visit[start_v] = 1
    
    #시작 노드와 연결되어 있는 노드 수
    total = 1
    
    while q:
        v = q.popleft()
        
        #현재 노드 v와 연결된 방문하지 않은 노드를 탐색한다
        for nv in graph[v]:
            if not visit[nv]:
                q.append(nv)
                visit[nv] = 1
                #새로운 노드를 탐색했으므로 total 카운팅
                total += 1
                
    return total


def solution(n, wires):
    answer = n
    
    #전선을 하나씩 끊어내기 위해 deque으로 변환
    d_wires = deque(wires)
    
    for _ in range(len(wires)):
    	#맨 앞의 전선을 끊는다
        broken_wire = d_wires.popleft()
        
        #그래프 탐색을 위해 초기화
        visit = [0] * (n + 1)
        #두 전력망에 속하는 송전탑의 개수를 담는 배열
        tops = []
        graph = defaultdict(list)
        for v1, v2 in d_wires:
            graph[v1].append(v2)
            graph[v2].append(v1)
            
        #그래프 탐색
        for v in range(1, n + 1):
        	#이전에 방문하지 않은 정점이면, 해당 정점을 기준으로 그래프 탐색을 시작한다
            if not visit[v]:
                tops.append(bfs(v, graph, visit))
        
        #두 전력망의 송전탑의 개수의 차보다 answer 값이 더 크다면, answer 값 갱신
        answer = min(abs(tops[0] - tops[1]), answer)
		
        #끊은 전선을 다시 붙여준다
        d_wires.append(broken_wire)
        
    return answer
    
#시간복잡도 = O(E(V+E)), 공간복잡도 = O(n)