[프로그래머스] DFS/BFS - 네트워크(python)

 

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

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

 

 

1. deque 활용 큐를 사용한 BFS 풀이

 

from collections import deque

def solution(n, computers):
    
    computers = deque(computers)
    network = 0
    global visited
    visited = [False] * n
    
    for k in range(n):
        if BFS(n, computers, k, visited)==True:
            network += 1
        
    return network

def BFS(n, computers, k, visited):
    
    if visited[k]==True:
        return False
    
    queue = deque([computers[k]])
    visited[k] = True
    
    while len(queue)>0:
        node = queue.popleft()
        for i in range(n):
            if i!=k and node[i]==1:
                if visited[i]==False:
                    visited[i] = True
                    queue.append(computers[i])
                    
    return True

 

TypeError: 'int' object is not subscriptable 부분에서 자꾸 막혔다.

보통 리스트가 아니라 숫자를 인덱싱하는 자료구조의 문제때문에 이런 에러가 나는 것으로 알고 있는데,

끝까지 발견 못해서 주피터로 일일이 확인..

computer의 이중리스트를 데큐로도 감싸줘야 했다..

 

2. 재귀를 활용한 DFS 풀이

 

def solution(n, computers):
    network = 0
    visited = [False] * n
    for num in range(n):
        if visited[num] == False:
            DFS(n, computers, num, visited)
            network +=1
    return network
            
def DFS(n, computers, num, visited):
    visited[num] = True
    for cnt in range(n):
        if num!=cnt and computers[num][cnt]==1:
            if visited[cnt]==False:
                DFS(n, computers, cnt, visited)