[프로그래머스] 네트워크 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43162

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

간단한 BFS 문제이다.

 

한지점에서 출발하여 도달할 수 있는 모든 지점은 같은 네트워크이다. 이때 네트워크의 개수를 구하는 것이다.

방문한 점을 방문 표시해주고 그 점에서 BFS를 시작한다. 이때 BFS를 몇번 돌렸는지 구하면 된다.

 

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [False]*n
    
    for start in range(n):
        if not visited[start]:
            answer += 1
            bfs(n,start,computers,visited)
    return answer

def bfs(n,start,computers,visited):
    q = deque([start])
    visited[start] = True
    while q:
        now = q.pop()
        for nxt in range(n):
            if now == nxt:
                continue
            if computers[now][nxt] == 1 and not visited[nxt]:
                visited[nxt] = True
                q.appendleft(nxt)