[DFS] 프로그래머스 Lv3. 네트워크 - Python

🗂️ 문제

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

프로그래머스

 

💡 접근법

노드를 최대한으로 방문하면 하나의 네트워크가 형성된다. 해당 네트워크의 개수를 구하는 문제이다.

DFS를 통해 한 번 탐색을 시작할 때 최대한으로 탐색한다. 또한 visited 리스트를 사용하여 노드 방문 여부를 체크한다.

 

😎 내 코드

def solution(n, computers):
    answer = 0
    
    visited = [False] * n
    def DFS(v):
        visited[v] = True
        for i, c in enumerate(computers[v]):
            if c == 1 and not visited[i]: # 컴퓨터가 연결되어 있고, 방문한 적 없을 때
                DFS(i)
    
    for i in range(n):
        if not visited[i]:
            DFS(i)
            answer += 1
        
    return answer