(Python) 프로그래머스 - 네트워크
in Algorithm on Programmers, Level3
[문제 링크]
풀이
from collections import deque
def solution(n, computers):
answer = 0
visit = [0] * n
start = 0
while 0 in visit:
if visit[start] == 0:
bfs(start, computers, n, visit)
answer += 1
start += 1
return answer
def bfs(start, computers, n, visit):
q = deque([start])
visit[start] = 1
while q:
start = q.pop()
for j in range(n):
if visit[j] == 0 and computers[start][j] == 1:
q.append(j)
visit[j] = 1
print(solution(4, [[1, 1, 0, 1], [1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 1, 1]]))
방문한 곳을 저장하는 리스트를 하나 만들고 노드 하나씩 선정해서 bfs를 돌리면 된다.