[알고리즘] queue 보다는 deque를 사용하자

# 발단

7569번: 토마토

[백준7569] 토마토라는 문제를 풀었다. BFS를 이용하여 탐색과 동시에 가장 빠르게 탐색을 완료하는 시점(단계)를 구하는 문제였다. 3차원이 주어진다는 것 외에는 그렇게 특별한 문제가 아니였기에, 매번 풀던방법과 같이 queue(큐)를 사용하여 문제를 풀었다.

 DFS는 스택, BFS는 큐를 사용하는 것이 나에게 있어서는 정석과도 같은 방법이었기 때문이다. 그런데 시간초과가 발생했다. 파이썬은 그럴 수 있기에 PyPy로 제출해봤는데 역시나 시간초과였다. 이런 경우 보통은 내 풀이가 잘못 된것이다. 질문게시판을 들어가서 다른 분들 코드를 조금 염탐했다. 구현 방식은 너무나도 비슷했고 queue대신 deque를 사용한 차이 밖에 없었다. 

 

# 결론

[Python] 파이썬 Queue와 deque 속도 /

결론은 deque가 더 빠르다. queue는 멀티쓰레드  환경을 지원하기 때문에 느리다고 했다. deque는 상수시간 O(1)의 시간복잡도를 가진다고 했다!

어쩐지 점찍어보면 mutex나 join같은게 보였다. 

deque로 바꾸니 깔끔히 python3에서도 정답이 나왔다!

 

# 참고

[Python] deque 사용법