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

 

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

프로그래머스

문제 요약 : 컴퓨터 개수, 연결정보가 담긴 computers 배열이 주어질 때 네트워크 개수를 return하라.

이 경우 네트워크는 2개이고

이 경우는 하나이다.

 

풀이 )

BFS로 풀었음!

check는 정점을 지나갔는지 아닌지를 표시했다.

 

모든 컴퓨터를 돌 수 있도록 n만큼 반복하였다. 단, 한 네트워크에 여러 컴퓨터가 연결되어 있기 때문에 불필요한 반복을 없애기 위하여 check되지 않은 컴퓨터만 돌도록 하였다.

 

check되지 않은 컴퓨터는 q에 넣고, BFS를 돌렸다.

먼저 q에 가장 앞에 있는 숫자를 꺼낸후(tmp), check표시를 해준다. 그다음 tmp를 기준으로 연결된 컴퓨터들 중 방문하지 않은 컴퓨터들을 p에 append해준다. q가 빌 때까지 반복한다. 그러면 한 네트워크가 끝나게된다. 이때 ans+=1를 해준다.

 

모든 컴퓨터들을 방문하고 나면 ans를 출력해준다.

from collections import deque

def solution(n, computers):    
    ans = 0
    check = [0]*n
    q = deque()
    
    for i in range(n):
        if check[i] == 0 :  # 방문 안한 컴퓨터만
            q.append(i)
            while q :
                tmp = q.popleft()
                check[tmp] = 1
                for j in range(n):
                    if (computers[tmp][j] == 1) and (check[j] == 0):
                        q.append(j)
            ans += 1
            
    
    return ans