문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162
bfs
전역변수 set으로 방문 노드 기록
코드
from collections import deque
check = set([0]) # 방문한 노드를 표시하는 집합
def bfs(i, computers, n):
global check
dq = deque()
dq.append(i)
while dq:
pop = dq.popleft()
for j in range(n):
if computers[pop][j]==1 and pop!=j and j not in check:
dq.append(j)
check.add(j)
return
def solution(n, computers):
global check
answer = 0
bfs(0,computers,n)
answer += 1
while len(check)!=n:
for i in range(n):
if i not in check:
check.add(i)
bfs(i,computers,n)
answer+=1
return answer상세
-
check 변수: 방문한 노드를 체크하는 역할을 하며, 처음에는 0번 컴퓨터를 네트워크에 추가하고 시작한다.
-
bfs 함수: 시작 노드(i), 컴퓨터들의 연결 정보(computers), 컴퓨터의 개수(n)를 인자로 받는다. 이 함수는 deque를 이용해서 bfs를 진행하며, 연결된 컴퓨터를 check 집합에 추가한다.
-
solution 함수: 첫 번째 네트워크를 찾기 위해 bfs 함수를 호출하고, 네트워크의 개수(answer)를 1 늘린다. 그 후, 모든 컴퓨터가 check 집합에 포함될 때까지 bfs를 계속 진행한다. 이때, 아직 방문하지 않은 컴퓨터를 찾아 bfs의 시작 노드로 설정하고, 네트워크 개수를 증가시킨다.
