[프로그래머스 43162 파이썬] 네트워크 (level 3, BFS/DFS)

알고리즘 유형 : BFS/DFS
풀이 참고 없이 스스로 풀었나요? : O

https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=python3

소스 코드(파이썬)

from collections import deque

def BFS(now, visited, n, computers):
    q = deque()
    q.append(now)
    visited[now] = True
    
    while q:
        v = q.popleft()
        
        for other_v in range(len(computers[v])):
            isLinked = computers[v][other_v]
            if isLinked and visited[other_v] == False:
                q.append(other_v)
                visited[other_v] = True
    
    return 1
                

def solution(n, computers):
    answer = 0
    visited = [False]*n
       
    for computer in range(n):
        if visited[computer] == False:
            answer += BFS(computer, visited, n, computers)
    
    return answer

풀이 요약

1. BFS로 풀었다. 모든 노드를 대상으로 BFS를 돌리면 된다.

   단, visited가 True인 노드는 BFS를 돌리지 않는다. 만약 어떤 노드를 BFS를 돌려고 했는데 visited가 True라면, 다른 노드에서 돌린 BFS가 이미 이 노드를 탐색한 상태임을 의미한다.

   BFS를 돌린 횟수가 곧 네트워크의 개수를 의미하므로, BFS에서 그냥 1을 리턴해주면 된다.

배운 점, 어려웠던 점

• 어떤 노드에서 뻗어나갈 인접 노드를 고르는 과정에서 computers 배열의 0, 1 여부를 고려하는 점, 그리고 인접 노드를 computers을 인덱싱할 때 사용한 두 번째 인자로 삼는 부분이 참신했다.