[프로그래머스]네트워크

구하려는 네트워크 갯수 > 트리의 갯수 > DFS/BFS 사용 가능

 

BFS

from collections import deque 
def BFS(n, computers,visited,i):
    q = deque()
    q.append(i)
    while q:
        k = q.popleft()
        visited[k] = True
        for i in range(n):
            if (k != i) and computers[k][i]  and (not visited[i]):
                q.append(i)
            
def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for i in range(n):
        if not visited[i]:
            BFS(n, computers,visited,i)
            answer+=1
    return answer

python 에서 list pop 메소드에 매개변수가 없으면 시간 복잡도가 O(1)이지만 매개변수가 있다면 O(N)이다

> deque를 쓰면 시간 복잡도를 개선할 수 있다.

DFS

def DFS(n, computers,visited,i):
    visited[i] = True
    for j in range(n):
        if j != i and computers[i][j] and not visited[j]:
            DFS(n, computers,visited,j)

            
def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for i in range(n):
        if not visited[i]:
            DFS(n, computers,visited,i)
            answer+=1
    return answer