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

문제링크

https://programmers.co.kr/learn/courses/30/lessons/43162

접근 방법

• 네트워크에 속한 모든 노드들을 방문한다면, 그 네트워크는 방문이 끝난 네트워크가 된다.
• dfs로 네트워크를 하나씩 돌면서 개수를 센다.

코드 (python)

def solution(n, graph):
    visited = [False] * n
    count = 0  # 네트워크 개수를 세는 변수

    def dfs(i):
        if visited[i]: # 방문 했다면 종료
            return

        visited[i] = True # 방문 처리 해준다
        for next_i, connected in enumerate(graph[i]):
            # 연결이 안됐거나, 자기 자신을 방문하거나, 이미 방문했으면 continue
            if not connected  \ 
                    or next_i == i \
                    or visited[next_i]:
                continue
            dfs(next_i)

    # 모든 노드를 돌면서 네트워크를 하나씩 방문한다
    for i in range(n):
        if not visited[i]:
            count += 1
            dfs(i)

    return count