파이썬에서 bfs는 어떻게 구현할까요? 이 말은 파이썬에서 어떻게 queue를 쓸까요? 와 같은 말입니다. collections에 deque가 있는데요. 그것을 이용하시면 됩니다. 예전에 list.pop(0)을 언급하면서 이야기를 잠깐 했던 기억이 나네요.

 

 

[관련글]

python에서 list.pop(0)을 쓰면 안 되나요?

 


 먼저, append 부터 소개해 드리겠습니다. 이것은 오른쪽에, 원소를 추가합니다. 이 상황을 그림으로 그려 보겠습니다.

 

 

 덱에 1만 있다고 해 봅시다. append(2)를 호출했다고 하면, 아래와 같이 될 겁니다.

 

 

 1 오른쪽에 2가 추가되었습니다. 즉, 현재 deque에서 가장 오른쪽에 있는 것은 군청색으로 표시된 2인 것입니다. 다음에, 또 append 3을 하면 아래와 같이 될 겁니다.

 

 

 2 오른쪽에 3이 추가된 상황입니다. 여기서 제일 오른쪽에 있는 원소는 3입니다. 1 오른쪽에 2, 2 오른쪽에 3이 있기 때문에, 3은 1의 우측에 있다고 볼 수 있습니다. 그러면 뺄 때 어떻게 할까요? 사실 큐는 뒤에 추가하고, 앞에서 빼는 구조입니다. 먼저 들어간 아이템이 먼저 나온다는 것은 알고 계실 텐데요.

 

 1은 2보다 먼저, 2는 3보다 먼저 들어간 상황입니다. 즉, 왼쪽에 있을 수록 먼저 들어간 거에요.

 


 왼쪽에 있는 것을 pop하는 popleft를 호출하면 됩니다.

 

 

 말 그대로 제일 왼쪽에 있었던 아이템을 제거하고, 그 값을 리턴합니다.

 

 

 제일 왼쪽에 있었던 것은 1이였습니다. popleft를 호출하면 1을 제거하고 1을 리턴합니다.

 

 

 그러면 deque에는 2, 3이 남았을 겁니다. 이 상태에서 또 popleft를 호출하였다면, 2가 제거되고 2가 리턴될 겁니다.

 


 이제, 사용법만 간단하게 보고, 성능이 준수한지만 보겠습니다.

 

 

 4번째 줄에 보면 queue.append(i)를 호출하는데요. 이것은 deque의 제일 오른쪽에 원소를 넣는 것을 의미합니다. 다음에, 7번째 줄에 queue.popleft()는 왼쪽에서 빼는데요. 넣는 곳과 빼는 곳이 반대임을 알 수 있어요. deque의 앞과 뒤. 반대 관계입니다. 왼쪽과 오른쪽도 반대 관계인 점이 같습니다.

 

 그런데, 6번째 줄에 while queue: 라는 이상한 문법이 있어요. 이것은 문서를 보면 나와 있는데요. 빈 콜렉션은 false로 간주한다고 되어 있어요. 즉, 아이템을 계속 빼다가, queue가 빈 상태면 6번째 while loop를 빠져나올 겁니다.

 

 

 실행 결과는 위와 같습니다. 하나 궁금한 것은, popleft가 효율적으로 동작하는지 입니다. 시간 측정을 해 보면 됩니다.

 

 

 queue에서 100만개의 데이터를 집어넣습니다. 그리고 100만개의 데이터를 빼는 것은 while loop에서 하는데요. while 루프 전후로 time을 측정하는 코드를 넣으면 됩니다. 8번째 줄과 12번째 줄이 그러한 일을 수행합니다.

 

 

 실행 결과는 위와 같습니다. 0.1207848은 100만개의 아이템을 빼는 데 걸린 시간을 의미하는데요. 생각보다 효율적으로 돌아가고 있음을 알 수 있습니다. 파이썬에서 큐를 쓸 때에는 list를 큐처럼 쓰는 게 아니라 deque를 쓰면 됩니다. 이 글도 추가로 읽어보시면 좋을 듯 싶습니다.