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

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

코딩테스트 연습 - 네트워크

def solution(n, computers):
    cnt = 0
    visited = [False for _ in range(n)]
    for com in range(n):
        if visited[com] == False:
            dfs(n,computers,com,visited)
            cnt += 1
    return cnt

def dfs(n, computers, com, visited):
    visited[com] = True
    for connect in range(n):
        if connect!=com and computers[com][connect] == 1: #연결된 컴퓨터
            if visited[connect] == False: #방문한적없으면 다시 탄다
                dfs(n, computers, connect, visited)

 

한눈만 뜨고 봐도 dfs로 푸는 문제

 

1. visited 생성

2. graph를 돌면서 돌기 시작하면 true로 visited update

3. 시작점을 돌면서 연결되어 있으면 갈건데, visited가  false면 간다 <-- dfs 재귀호출