백준24444 - 알고리즘 수업 - 너비우선탐색1 (deque) Python

https://www.acmicpc.net/problem/24444

문제는 너비우선탐색을 구현하여, 각 정점의 방문순서를 출력하는 문제다.

너비우선탐색 문제 풀이 대해 포스팅을 몇 번 진행한 적 있지만, 이번 포스팅에서는 파이썬 내장모듈인 deque에 대해 소개한다.

 

deque는 double-end queue의 약자로 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조를 말한다.

deque는 collections 모듈에 포함되어 있으며 리스트와 유사한 동작을 수행하지만 효율적인 연산을 제공한다.

 

개인적으로 생각하는 deque와 리스트의 큰 차이점은 맨앞에서 요소를 제거할 때인데,

이때, n이 전체 길이라고 한다면 deque는 O(1)의 시간복잡도, 리스트는 O(n)의 시간복잡도로 처리된다는 것에 있다.

(리스트의 경우 맨앞 요소를 삭제하는 것이 아닌, 앞 순서에 뒷 요소를 재할당하는 과정을 거치는 방식으로 동작하기 때문)

 

따라서 본 문제와 같이 정점의 수가 최대 10만인 경우, 

리스트로 큐를 구현하고 맨앞에서 요소를 제거하는 과정을 거친다면 매번 O(10만)의 매우 높은 시간복잡도가 우려된다는 얘기기도 하다.

 

deque에서 사용하는 메서드는 리스트에서 사용하는 메서드 명과 크게 다르지 않다.

from collections import deque

# 선언
queue = deque()

# 오른쪽 끝 아이템 추가
queue.append(n)

# 왼쪽 끝 아이템 추가
queue.appendleft(n)

# 오른쪽 끝 아이템 삭제
queue.pop()

# 왼쪽 끝 아이템 삭제
queue.popleft()

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
from collections import deque

def solution (data) :
  N,M,R = map(int,data.pop(0).split())
  arr = list(map(lambda x : list(map(int, x.split())), data))
  arr.sort(key= lambda x : [x[0],x[1]])

  graph = [[] for _ in range(N+1)]

  for [to,go] in arr :
    graph[to].append(go)
    graph[go].append(to)

  def BFS (startNode) :
    visited = {}
    queue = deque([startNode])
    idx = 1
    while len(queue) :
      node = queue.popleft()
      if not visited.get(node, 0) :
        visited[node] = idx 
        idx += 1
        for next in graph[node] :
          if not visited.get(next,0) : queue.append(next)

    matrix = [0 for _ in range(N)]
    for (k,v) in visited.items() :
      matrix[k-1] = v

    return matrix

  result = BFS(R)
  print('\n'.join(map(str, result)))

solution(input_data)