프로그래머스 DFS/BFS, 네트워크(Level3) with Python

오늘 풀어볼 문제는 코딩 테스트 고득점 Kit에 들어있는 DFS/BFS - 네트워크입니다.

개인적으로는 이 문제는 여행경로와는 다르게 레벨 3치고는 엄청 쉬운 편(?) 인 것 같습니다.

programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

문제 설명 & 제한사항

 

접근 방식:

1. 주어진 2차원 배열을 갖고 그래프를 만듭니다. 

2. 탐색을 해야 하므로 BFS함수를 작성합니다. 모든 탐색이 끝난 후 그래프에서 방문한 노드를 삭제해 줍니다. 한 번의 탐색 완료가 곧 하나의 네트워크 탐색을 의미하므로 1을 리턴해줍니다. 

3. 그래프를 다 탐색할 때까지(모든 네트워크를 구할 때까지) 반복해 줍니다. 

-끝-

 

파이썬 코드

import collections

def solution(n, computers):  
    answer = 0
    
    #1
    graph = collections.defaultdict(list)
    
    for i in range(len(computers)):
        graph[i] = list(filter(lambda x: x != i and computers[i][x] == 1, range(n)))
    
    #2 
    def BFS(graph, root):
        queue = collections.deque()
        visit = []
    
        queue.append(root)
    
        while queue:
            node = queue.popleft()
        
            if node not in visit:
                visit.append(node)
                queue.extend(graph[node])
        
        for v in visit:
            del graph[v]
        return 1
    
    #3
    while graph:
        answer += BFS(graph,list(graph.keys())[0])
        
    return answer