프로그래머스 | 네트워크 (Python)

프로그래머스

 

dfs로 풀어야겠다는 생각은 바로 들었는데 인접리스트랑 dfs 구현 중 자잘한게 생각이 안나서 생각보다 풀이시간이 많이 걸렸다.

 

내 코드

def dfs(graph, start, visited):
    visited.append(start) 
    
    for node in graph[start]:
        if node not in visited:
            dfs(graph, node, visited)
    
    return visited
            

def solution(n, computers):
    answer = 0
    # 인접리스트로 그래프 표현
    graph = {i:[] for i in range(n)}
    
    for i in range(n):
        for j in range(len(computers[i])):
            if (computers[i][j] == 1) and (i != j):
                graph[i].append(j)
    
    # 깊이 우선 알고리즘(dfs)를 통해 연결된 네트워크 수 카운트
    visited = []
    
    # dfs의 결과로 연결된 네트워크가 출력됨
    for i in range(n):
        if i not in visited:
            network = dfs(graph, i, visited)
            answer += 1
    
    return answer