[프로그래머스] Lv3. 네트워크

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

코드

from collections import deque
def solution(n, computers):
    answer = 0
    visited = [False] * n
    q = deque()
    for i in range(n):
        if visited[i] == False:
            q.append(i)
            while q:
                tmp = q.popleft()
                visited[tmp] = True
                for x in range(n):
                    if x != tmp and computers[tmp][x] == 1:
                        if visited[x] == False:
                            q.append(x)
            answer += 1
    return answer

풀이

• dfs,bfs 둘 다 풀 수 있지만 개인적으로 프로그래머스에서는 bfs가 편해서 bfs로 해결했다.
• n개의 컴퓨터만큼 for문을 돌아 아직 방문하지 않은 컴퓨터가 있으면 큐에 넣고 탐색을 시작한다.
• 탐색 조건은 자기 자신을 빼고, 해당 노드와의 값이 1이면서, 아직 방문하지 않은 노드이면 큐에 넣는다.