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

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

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

참고

https://hkim-data.tistory.com/31?category=1016184 

#2-3 Python 코딩테스트 그리디 알고리즘 , DFS & BFS

 

DFS (재귀함수 활용)

def solution(n, computers):
    visited = [False] * n
    answer = 0
    def dfs(computers, visited, now):
        visited[now] = True #현재위치 방문 표시
        for v in range(len(computers)):
            if visited[v] == False and computers[now][v] == 1:
                #방문하지 않았고 , 컴퓨터가 연결되어 있을 경우
                dfs(computers, visited, v)
                    
    while False in visited: # 모두 방문할때 까지
        for i in range(n): # 전체 탐색
            if visited[i] == False: # 방문하지 않았을 경우 
                dfs(computers, visited, i)# 탐색
                answer += 1
    return answer

 

DFS (스택 활용)

def dfs(idx,computers,visited):
    stack = [idx]
    while stack:
        idx = stack.pop()
        visited[idx] = True        
        for j in range(len(computers[idx])):
            if visited[j] == False and computers[idx][j] == 1:
                stack.append(j)

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

 

BFS (queue 활용)

from collections import deque

def solution(n,computers):
    answer = 0
    visited = [False for _ in range(n)]
    for i in range(n):
        if visited[i] == False:
            visited[i]=True
            queue = deque([i])
            print(queue)
            answer += 1
        while queue:
            idx = queue.popleft()
            visited[idx]=True
            for j in range(len(computers[idx])):
                if visited[j] == False and computers[idx][j] == 1:
                    queue.append(j)
    return answer