네트워크

• 커넥티드 컴포넌트의 갯수를 찾는 문제.
• 특정 노드와 연결된 노드를 모두 찾는 것은 BFS와 DFS중 어느 방법으로든 가능하지만, 여기서는 DFS를 사용.
• 커넥티드 컴포넌트의 갯수에 관계 없이, 모든 노드를 1번씩 방문하게 되므로, 시간 복잡도는 O(V+E)이다. 여기에서는 E = O(V^2) 이므로 전체 시간복잡도도 O(V^2)이다.

"""Solution code for "Programmers 43162. 네트워크".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43162
- Solution link: http://www.teferi.net/ps/problems/programmers/43162
"""

from teflib import search


def solution(n, computers):
    def next_states(u):
        return (v for v, is_connected in enumerate(computers[u])
                if is_connected == 1)

    is_visited = [False] * n
    answer = 0
    for u in range(n):
        if is_visited[u]:
            continue
        for node in search.simple_dfs(next_states, u):
            is_visited[node] = True
        answer += 1
    return answer

• Dependency: teflib.search.simple_dfs