[프로그래머스] 네트워크 (level3, python)

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

프로그래머스

아이디어

dfs를 사용해서 풀었다.

visited 방문 리스트를 만들어서 탐색을 하며 방문한 인덱스를 1로 변경해주었다.

 

visited[idx] 가 0이면 dfs 시작

    visited = [0] * n

방문 리스트는 컴퓨터 갯수만큼 만들어준다.

    count = 0
    for idx in range(n):
        if visited[idx] == 0:
            count += 1
            dfs(idx, computers[idx])

방문 리스트가 0이면 dfs 탐색을 시작한다. (1이면 이미 탐색된 곳이므로 path)

 

 

dfs 탐색

    def dfs(depth, cans): 
        nonlocal computers, visited
        
        if visited[depth] == 1: return
        visited[depth] = 1 
        
        for idx, can in enumerate(cans):
            if idx == depth: continue
            if can == 1: 
                dfs(idx, computers[idx])

우선 depth는 컴퓨터 번호(idx)이고,

cans는 해당 depth에 해당하는 컴퓨터(idx)의 연결 정보이다.

 

1. 만약 해당 depth에 해당하는 컴퓨터를 이미 방문했다면 그냥 return을 한다.
2. 아니라면 depth에 해당하는 방문노드를 1로 변경해주고 
3. cans(연결정보)를 돌면서 방문 가능한(1) 컴퓨터를 모두 방문해준다.
   1. 이때 자기 자신의 경우(idx==depth) 항상 1이므로 continue로 넘겨준다.

위 로직을 지나면 연결된 모든 컴퓨터의 방문 정보가 1이 된다. 

다음 네트워크를 찾기 위해서는 방문 리스트를 돌면서 0인 부분부터 다시 위 로직을 시작하면 된다.

 

즉, dfs의 호출 횟수가 네트워크의 수 이다. 

 

 

전체 코드

def solution(n, computers):
    visited = [0] * n

    def dfs(depth, cans): 
        nonlocal computers, visited
        
        if visited[depth] == 1: return
        visited[depth] = 1 
        
        for idx, can in enumerate(cans):
            if idx == depth: continue
            if can == 1: 
                dfs(idx, computers[idx])
    
    
    count = 0
    for idx in range(n):
        if visited[idx] == 0:
            count += 1
            dfs(idx, computers[idx])
        
    return count