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

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

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

 

문제 설명

BFS를 이용해 연결된 모든 컴퓨터를 탐색하는 방법으로 문제를 해결했습니다. 

1. 방문하지 않은 컴퓨터 중 작은 번호부터 BFS 수행
2. BFS가 끝나면 네트워크 개수 1 증가 (answer++)
3. 방문하지 않은 컴퓨터가 없을 때까지 1~2번을 반복 수행

 

 

 

소스코드

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [False] * n

    def bfs(start, visited, computers):
        visited[start] = True
        queue = deque([start])
        while queue:
            v = queue.popleft()
            for i in range(n):
                # 방문하지 않은 연결된 컴퓨터
                if computers[v][i] == 1 and not visited[i]:
                    visited[i] = True
                    queue.append(i)

    # 방문하지 않은 컴퓨터 중 작은 번호부터 BFS 수행
    for i in range(n):
        if not visited[i]:
            bfs(i, visited, computers)
            answer += 1

    return answer