[프로그래머스] 네트워크 _ 파이썬

BFS를 이용해 재귀를 사용하지 않은 문제이다.
오늘도 바로 풀기는 실패.. 다른 분 풀이를 읽고 풀었음

DFS, BFS 중 어떤 방법을 이용할까?
둘 다 연결된 그래프를 모두 탐색할 때 사용

• DFS
  1. 특정 조합을 뽑는 경우
  2. DFS는 그래프의 모든 정점을 확인하기 때문에 한정 조건이 있는 문제에서는 비효율적이다.
  3. 한 가지 정점과 연결된 모든 정점을 탐색해야 하는 경우
  4. 경로를 찾아야 하는 경우
  5. 사이클이 존재하는 경로 찾는 경우
• BFS
  1. 특정 그래프에서 가중치가 모두 같은 경우 최단거리 찾기 가능

-> 깊이를 파악할 필요 없는 문제이고 그냥 전체 탐색을 하면 되기 때문에 BFS 사용

BFS 구현 방법
-> 주로 queue를 이용해서 구현
1. 인접 행렬을 저장할 queue, 다녀간 정점을 확인하기 위한 배열이 필요
2. 탐색을 시작할 노드를 queue에 삽입하고 다녀갔음을 확인용 배열에 표시
3. 시작 노드의 인접 노드들을 queue에 삽입하고 queue가 빌 때 까지 2번을 반복
4. 다녀가지 않은 노드를 확인해 모든 노드를 다녀갈 때 까지 2~3 과정을 반복

from collections import deque

def solution(n, computers):
    answer = 0
    queue = deque()
    check = [True for i in range(n)]
    
    while True in check:
        first = check.index(True)
        queue.append(first)
        check[first] = False

        while queue:
            now = queue.popleft()

            for i in range(n):
                if check[i] and computers[i][now] == 1:
                    queue.append(i)
                    check[i] = False
        answer += 1
        
    return answer

루트 노드가 같을 경우 전부 하나의 네트워크에 포함됨.
그래서 answer += 1 은 두번째 while문이 돌고난 후 추가