프로그래머스 / 네트워크 / python

def solution(n, computers):
    def dfs(x):
        visited[x] = True
        
        for i in graph[x]:
            if not visited[i]:
                dfs(i)
    
    answer = 0
    graph = [[] for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            elif computers[i][j] == 1:
                graph[i].append(j)
                
    visited = [False] * n
    
    for i in range(n):
        if not visited[i]:
            answer += 1
            dfs(i)
    
    return answer

DFS로 문제 해결

n의 최대 개수가 200이므로 dfs로 접근하여도 recursion limit에 제한 받지 않으므로 dfs로 해결

이 문제는 dfs의 깊이가 아닌 횟수로 답을 구할 수 있는 문제이다. dfs를 진행한 횟수를 구함으로서 분리되어 있는 노드들의 묶음(이 문제에서는 네트워크)를 구할 수 있다.