[Programmers | Level 3] 네트워크 (Python)

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

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

from collections import deque

def solution(n, computers):
    visited = [False] * n
    q = deque()
    cnt = 0
    for i in range(n):
        if not visited[i]:
            q.append(i)
            visited[i] = True
            cnt += 1
            while q:
                v = q.popleft()
                for i in range(n):
                    if not visited[i] and computers[v][i] == 1:
                        q.append(i)
                        visited[i] = True
    return cnt

BFS를 이용하였다.

컴퓨터의 번호를 0~n-1까지 돌면서 방문한적 없는 컴퓨터에 대해서 cnt값을 늘려주었다.

각각에 대해서 연결된 컴퓨터를 bfs하였고, 방문처리를 해서 다음번 탐색때 cnt값이 늘어나지 않도록 했다.

이렇게 해서 같은 네트워크 상의 컴퓨터들은 한번씩만 카운트하게 된다.