문제 출처 : 프로그래머스 네트워크

문제 접근

여러 컴퓨터들이 연결되어있는 인접행렬(computers)를 탐색하며 방문 표시
각 컴퓨터마다 탐색하여 같은 네트워크에 있는 컴퓨터를 모두 방문표시한다.
아직 방문하지 않은 컴퓨터에서 한번 탐색이 끝나면 하나의 네트워크를 찾은것이다.

같은 네트워크를 한번의 탐색으로 찾기 위해 DFS 그래프 탐색 알고리즘을 사용한다.

재귀

def DFS(computers, visited, now):
    visited[now] = True
    
    for i in range(n):
        if computers[now][i] and not visited[i] and i != now:
            DFS(n, computers, visited, i)
        

def solution(n, computers):
    networks = 0
    visited = [False] * n
            
    for i in range(n):
        if not visited[i]:
            DFS(computers, visited, i)
            networks += 1
    
    return networks

스택 (List)

def DFS(computers, visited, now):
    stack = [now]
    visited[now] = True

    while stack:
        now = stack.pop()
        for i, connected in enumerate(computers[now]):
            if connected and not visited[i]:
                visited[i] = True
                stack.append(i)

def solution(n, computers):
    networks = 0
    visited = [False] * n
            
    for i in range(n):
        if not visited[i]:
            DFS(computers, visited, i)
            networks += 1

    return networks

스택 (Deque)

from collections import deque

def DFS(computers, visited, now):
    stack = deque([now])
    visited[now] = True

    while stack:
        now = stack.pop()
        for i, connected in enumerate(computers[now]):
            if connected and not visited[i]:
                visited[i] = True
                stack.append(i)

def solution(n, computers):
    networks = 0
    visited = [False] * n
            
    for i in range(n):
        if not visited[i]:
            DFS(computers, visited, i)
            networks += 1

    return networks

Stack을 만들때 List를 많이 사용하는데 어떤 블로그에서 List보다 Deque가 성능이 좋다고 사용했다고 해서 궁금했다.

Deque는 양방향에서 삽입,삭제하는데 장점을 갖는 이중 연결 리스트로 구현되어있는 자료구조이다.
어차피 stack은 끝쪽에서 삽입 삭제가 이루어져야하는 자료구조로 List를 사용하더라도 성능상 차이가 크지 않을것 같다.

[두 자료구조 모두 시간 복잡도: O(1)]

그러면 삽입, 삭제시 메모리 관리 측면에서 두 자료구조의 차이점을 생각해 볼 수 있을것 같다.

• List

  • Python에서 리스트는 동적 배열로 배열 할당시 고정된 size의 연속된 메모리 공간을 할당하여 사용한다.
  • 공간이 부족해지면 좀 더 큰 배열을 만들고 이전 배열을 복사해온다.
    주어진 데이터의 공간보다 더 큰 공간을 차지하여 공간 낭비가 발생할 수 있다.

• Deque

  • 이중 연결 리스트이기 때문에 메모리의 공간이 연속적이지 않다.
    메모리 단편화 현상이 발생할 수 있다. (OS 메모리 할당 전략으로 보안)
  • block 크기만큼 만들어서 연결하고 해제를 하여 주어진 데이터 공간 만큼 공간을 차지한다.

메모리 재할당 비용 측면에서 List보다 Deque가 더 효율적인것 같다.