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

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

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

BFS문제이다.

 

from collections import deque
def solution(n, computers):
    cnt = 0
    visited = [False] * (n+1)
    graph = [[] for _ in range(n)]
    q = deque()
    # 연결되어 있는 컴퓨터 graph에 저장
    for i in range(n):
        for j in range(n):
            if computers[i][j]:
                graph[i].append(j)
            
    for i in graph:
        # bfs를 돌며 연결된 네트워크 개수 cnt를 세줌
        for j in i:
            if not visited[j]:
                cnt += 1
                q.append(j)
                visited[j] = True
                while q:
                    x = q.popleft()
                    for k in graph[x]:
                        if not visited[k]:
                            q.append(k)
                            visited[k] = True
    return cnt

 

(프로그래머스 level: 3)