프로그래머스_네트워크

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

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

 

◎ Code

from collections import deque

def solution(n, computers):
    
    check_network = [False for _ in range(n)]
    answer = 0

    def bfs(index) :
        
        queue = deque()
        queue.append(index)
        while queue :
            index = queue.popleft()
            check_network[index] = True

            for i in range(n) :
                if check_network[i] == False and computers[index][i] == 1 :
                    queue.append(i)

    for i in range(n) :
        if check_network[i] == False :
            bfs(i)
            answer += 1
    
    return answer

 

◎ Code 설명

- BFS (Breadth-First-Search)

- 0번 컴퓨터부터 n-1 컴퓨터까지 방문한 적이 없는 노드를 기준으로 BFS탐색을 시작한다

- 위 과정에서 탐색하는 컴퓨터에 대해 방문 기록을 check_network 리스트에 저장하여 재방문 하는일이 없도록 한다

- BFS탐색을 한번 끝낼때 마다 네트워크의 수를 저장하는 answer에 1을 누적한다

- 위 과정을 반복하면 최종적으로 네트워크의 수를 구할 수 있다