[Programmers] 깊이/너비 우선 탐색 > 네트워크

Programmers에서 제공하는 깊이/너비 우선 탐색 네트워크

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

문제

풀이

from collections import deque

def solution(n, computers):
    answer = 0
    graph = {}
    for i, li in enumerate(computers):
        graph[i] = li
    
    for j in range(n):
        if j in graph:
            li = BFS_with_adj_list(graph, j)
            for m in li:
                graph.pop(m)
            answer += 1
    
    return answer


def BFS_with_adj_list(graph, key):
    visited = []
    queue = deque([key])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            for i, v in enumerate(graph[n]):
                if v == 1:
                    queue.append(i)
                    
    return visited

파이썬을 활용했고 노드들끼리 연결된 네트워크를 찾고 개수를 카운팅 하기 위해서 DFS 알고리즘을 이용했습니다. 알고리즘을 이용하면서 Queue를 활용하기 위해서 deque를 import해서 이용 했고 연결되어 있는 노드들을 찾고 해당 노드들을 그래프에서 제거하고 answer의 값을 늘려가는 방법을 사용했습니다.

다른 사람들의 문제풀이

def solution(n, computers):
    answer = 0
    visited = [0 for i in range(n)]
    def dfs(computers, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j] == 0:
                visited[j] = 1
            # for i in range(len(computers)-1, -1, -1):
            for i in range(0, len(computers)):
                if computers[j][i] ==1 and visited[i] == 0:
                    stack.append(i)
    i=0
    while 0 in visited:
        if visited[i] ==0:
            dfs(computers, visited, i)
            answer +=1
        i+=1
    return answer

stack을 활용해서 DFS 알고리즘을 활용하여 문제를 푼 것을 알 수 있습니다.

저의 풀이법과 차이는

주어진 computers 라는 List를 graph인 dictionary 형태로 변환 후 문제를 해결하거나 주어진 computers 형태를 그대로 이용하는 가 였습니다.

같은 결과를 가져오지만 아무래도 주어진 형태를 그대로 이용하는 것이 메모리와 시간 부분에서 절약이 되겠죠??

앞으로는 주어진 자료와 정보를 그대로 이용하는 코딩을 하는 것에 집중해보겠습니다!

감사합니다