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

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

프로그래머스

 

이번 문제는 DFS로 해결하였다.

양방향이기 때문에 visited 리스트 만들어서 방문 여부를 확인해 주기만 하면 된다. (일차원)

dfs를 돌 때, 스스로의 노트에 대해서 dfs를 돌게 되면 무한 루프가 돌게 될까봐 걱정을 하였다. [1][1] -> [1][1] 

하지만, 초기에 visited[node] = True 로 대입 후, dfs를 시작하기 때문에 그럴 염려는 하지 않아도 되었다.

 

def dfs(node, size, computers, visited):
    visited[node] = True
    
    for i in range(size):
        if (not visited[i]) and computers[node][i] == 1:
            dfs(i, size, computers, visited)
    
def solution(n, computers):
    networks = 0
    visited = [False] * n
    
    for i in range(n):
        if not visited[i]:
            dfs(i, n, computers, visited)
            networks += 1
            
    return networks