[programmers] 네트워크

---

로직

문제가 처음에 잘 이해가 안갔다,,,(난 바보다.,,)

n = 3
computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
답 : 2 -> why? 1,2가 하나의 네트워크, 3이 하나의 네트워크

n = 3
computers = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
답 : 1 -> why? 1,2,3이 하나의 네트워크

 

 - visit으로 확인하면서 bfs를 사용한다. 방문한 곳(i)은 visit[i] = 1로 바꿔주고 bfs를 이용하면서 연결된 부분을 찾아낸다.

   bfs문에 들어간 횟수 = 네트워크 갯수이다. 따라서 while을 한번 다 돌면 cnt += 1을 해준다

 

코드

from collections import deque

def solution(n, computers):
    visit = [0] * n
    cnt = 0
    q = deque()
    for i in range(n):
        if visit[i] == 0:
            q.append(i)
            visit[i] = 1

            # bfs문에 들어간 횟수 = 네트워크 갯수
            while q:
                x = q.popleft()
                for j in range(n):
                    if computers[x][j] == 1 and visit[j] == 0:
                        visit[j] = 1
                        q.append(j)

            cnt += 1

    return cnt