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

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

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

 

Point : 노드끼리 연결 상태(네트워크) 파악하기! -> 네트워크의 총 개수 찾기

자료 구조 : visited

(이미 연결된 네트워크가 있는 지 확인하는 용도로 visited = [False] * n을 사용함)

 

이 문제는 그래프의 연결 상태를 파악해야 하므로 BFS, DFS 둘 다 가능하다.

1. DFS : 재귀적으로 네트워크 연결상태 파악

2. BFS : 큐 사용해서 네트워크 연결상태 파악

 

 

 

1. DFS 사용한 풀이 : 재귀적으로 탐색

def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    def dfs(start):
        visited[start] = True
        for i in range(n):
            if i != start and computers[start][i] == 1 and visited[i] == False:
                dfs(i)
  
    for i in range(n):
        if visited[i] == False:
            dfs(i)
            answer += 1
    
    return answer

 

 

2. BFS 사용한 풀이 : 큐 사용해서 연결 노드 탐색

 

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