[프로그래머스/Python] - Lv3 / 네트워크

level3 - DFS/BFS - 네트워크

from collections import deque
def solution(n, computers):
    #n은 노드 개수 computers는 2차원 그래프
    g = computers
    ch = [0] * n
    
    def DFS(v):
        ch[v] = 1
        for i in range(n):
            if g[v][i] == 1 and ch[i] == 0:
                DFS(i)
                
    def BFS(v):
        ch[v] = 1
        dq = deque()
        dq.append(v) #시작노드
        
        while dq:
            now = dq.popleft()
            for i in range(n):
                if g[now][i] == 1 and ch[i] == 0:
                    ch[i] = 1
                    dq.append(i)
        
    cnt = 0
    for i in range(n):
        if ch[i] == 0:
            # DFS(i)
            BFS(i)
            cnt += 1
    return cnt

코멘트

해당 문제는 연결요소의 개수를 구하는 문제였다. 그렇기에 DFS/BFS 모두 사용가능!
각 노드별로 DFS의 경우 방문 체크 이후에 인접 노드와 연결되어 있으면 다시 DFS로 파고 들어가서 연결요소의 개수를 구하면 된다 !

BFS 역시 시작노드를 기준으로 체크해준 후에 인접노드가 있다면 방문 표시 이후에 데크에 append해줘서 다시 그 안에서 방문 안한 노드가 있으면 찾으면서 연결요소 개수 구하면 돼 !