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

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

코드

import queue
def solution(n, computers):
    answer = 0
    check=[0]*n
    q=queue.Queue()
    for i in range(n):
        if check[i]==1:
            continue
        q.put(i)
        while q.qsize():
            ck=q.get()
            check[ck]=1
            for i in range(n):
                if computers[ck][i]==1 and check[i]==0:
                    q.put(i)
        answer+=1
    return answer

bfs로 풀었다.

0번 부터 연결되어 있는 모든 컴퓨터를 방문해서 check를 1로 바꾼다.

이렇게 check가 1이 된 컴퓨터들이 한 개의 네트워크다.

이미 방문해서 check가 1이 된 컴퓨터는 다시 확인할 필요가 없기 때문에 continue 해준다.

이렇게 한번도 방문하지 않았던 컴퓨터 무리들을 탐색하면 네트워크의 수가 나온다.

Discussion and feedback