[DFS] 프로그래머스 - 네트워크 / python

문제링크

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

문제

입출력

💡 사고의 흐름

• computers -> 연결 상태에 대한 행렬 (nxn)
• computers의 값이 1일 때 dfs를 동작 (이때, 카운팅을 해주어 dfs에 들어가는 시점을 셀 수 있도록 한다.)
• dfs에 들어가는 시점은 새로운 네트워크가 들어가는 것.(연결되지 않은 컴퓨터가 새롭게 들어가는 경우) --> 즉, 구하고자 하는 네트워크 수가 나온다.

Code

def dfs(n, graph, node, check):
    check[node]=True
    for i in range(n):
        if graph[node][i]==1 and i!=node and check[i]==False:
            check[i]=True
            dfs(n,graph,i,check)
                
def solution(n, computers):
    answer = 0
    check = [False]*n
    for i in range(len(computers)):
        for j in range(len(computers)):
            if computers[i][j] ==1 and check[i]==False:
                answer+=1
                dfs(n,computers,i,check)
    return answer