PG) 네트워크 - lv3

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

프로그래머스

 

from collections import deque

def solution(n, computers):
#     아이디어
# 큐를 이용한다
# 배열 하나를 만들어(arr) 그 배열에 이어져있는 관계를 저장
# 어차피 서로 연결되어 있으니 둘 모두를 저장할 필요 없이 한 쪽만 저장하면 됨
# visit으로 방문여부 체크
# visit을 돌며 False은 값 찾아서 answer += 1
# bsf이후에 False라면 그 어떠한 것도 이어져있지 않으니 그 자체로 네트워크임
# 그 외 bsf
    answer = 0
    arr = [[] for _ in range(n)]
    
    visit = [False for _ in range(n)]
    
    for i in range(len(computers)):
        for j in range(len(computers[i])):
            if i == j:
                continue
            if computers[i][j] == 1:
                arr[i].append(j)
    
    cnt = 0
    for i in range(len(arr)):
        for j in range(len(arr[i])):
            if visit[arr[i][j]] == False:
                cnt += 1
                visit[arr[i][j]] = True
                
                q = deque()
                q.append(arr[i][j])
                while q:
                    idx = q.popleft()
                    
                    for nxt in arr[idx]:
                        if visit[nxt] == False:
                            visit[nxt] = True
                            q.append(nxt)
                
        
    for i in visit:
        if i == False:
            cnt += 1
    
    return cnt