코드
from collections import deque
def bfs(visited, computers, n, start):
q = deque([start])
while q:
now = q.popleft()
for i in range(n):
if computers[now][i] == 1 and not visited[i]:
q.append(i)
visited[i] = True
def solution(n, computers):
answer = 0
visited = [False] * n
q = deque([])
for i in range(n):
if not visited[i]:
visited[i] = True
bfs(visited, computers, n, i)
answer += 1
return answer
컴퓨터를 0번부터 탐색하는데 BFS로 같은 네트워크에 연결된 컴퓨터들을 탐색하며 방문한 컴퓨터들은 visited란 배열에 방문했다고 체크해준다. 이미 방문한 네트워크에 속한 컴퓨터라면 solution 안의 for문에서 본인 순서가 되어도 이미 visited[i]의 값이 True일 것이므로 그냥 지나간다. 따라서 bfs가 실행되는 횟수가 네트워크의 개수이다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 프로그래머스 타겟 넘버 (0) | 2022.12.02 |
---|---|
[Python/파이썬] 프로그래머스 단어 변환 (0) | 2022.10.21 |
[Python/파이썬] 2022 KAKAO BLIND RECRUITMENT 양궁대회 (0) | 2022.10.12 |
[Python/파이썬] 백준 16724번 피리 부는 사나이 (1) | 2022.10.06 |
[Python/파이썬] 백준 14503번 로봇 청소기 (0) | 2022.10.02 |