[프로그래머스] 네트워크 by 파이썬 (Python) : DFS(깊이 우선 탐색)

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

프로그래머스

 

난이도

LV3

 

 

문제 설명

• 컴퓨터 n 개가 주어지고 연결된 컴퓨터의 정보가 주어진다.
• 서로 연결된 컴퓨터끼리는 하나의 네트워크로 본다.
• 총 네트워크의 갯수를 Return 해줘야 한다.

 

접근법

• dictionary에 해당 컴퓨터 (key)에 대해 연결 된 컴퓨터(value)로 저장한다.
• 모든 컴퓨터를 하나씩 확인하며 방문하지 않았다면 탐색을 위해 DFS를 호출한다.
• DFS 깊이 우선 탐색을 이용해 시작 컴퓨터로 부터 깊이 탐색해 연결된 컴퓨터들을 방문 처리한다.
• DFS는 deque로 구현해 해당 key 컴퓨터에 대한 value 컴퓨터들을 방문 처리 해주고 queue에 추가해준다.

 

 

코드

from collections import deque
def solution(n, computers):
    answer = 0
    visited = []
    dic = {i:[] for i in range(n)}
    
    for i in range(len(computers)):
        for j in range(len(computers[i])):
            if i!=j and computers[i][j] == 1:
                dic[i].append(j)
                
    for i in range(n):
        if i not in visited:
            dfs(i,visited,dic)
            answer += 1
            
    return answer 

def dfs(start,visited, dic):
    q = deque()
    q.append(start)
    while q:
        x = q.pop()
        for i in dic[x]:
            if i not in visited:
                visited.append(i)
                q.append(i)

 

---

 

DFS(깊이 우선 탐색) ?

https://h-castle.tistory.com/entry/DFS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-DFS

[DFS] 알고리즘 - 깊이 우선 탐색 (DFS)