Deque 개념 정리 + BFS(너비 우선 탐색) 알고리즘 정리

Deque는 bfs 함수를 구현할 때, 거의 필수로 쓰이기 때문에 개념을 정리해보려고 한다.

우선, Deque란?
스택이나 큐처럼 한 방향에서 삽입 삭제가 일어나지 않고, 양방향에서 삽입 삭제가 가능하다.

https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki

리스트에서 삭제 삽입이 자유로운데, 굳이 스택,덱 을 쓸 필요가 있을까?
위 문서를 보면,
list에서 삭제연산은 O(n), deque에서 삭제는 O(1)만큼 걸린다.
작은 연산일 땐 괜찮지만, 연산량이 복잡하고 커질수록 시간복잡도를 낮추는 것만큼 중요한 게 없을 것이다.

왜 ? list에서 요소를 삭제하는데 O(n)이나 걸리게 되는 것일까?
list에서 하나의 요소를 삭제할 때, 그 요소만 빠지는 것이 아닌, 그 요소를 지우고 모든 요소를 앞으로 당겨준다. 그렇기에 O(n)이 걸리게 되고, 이것이 바로 덱(deque)를 써야하는 이유이다.

---

Deque를 잘 쓰기 위해 Deque 자주 쓰이는 함수에 대해 알아보자.

- 삽입 (append( 값 ), appendleft( 값 ))

from collections import deque

q = deque([1,2,3,4])
q.append('5')
q.appendleft('0')
print(q)

결과 : ['0', 1,2,3,4, '5' ]

- 삽입 ( insert( 위치, "요소" ) )

q = deque([1,2,3,4])
q.insert(2,"hello")
print(q)

2번째에 hello를 넣어준다.
결과 : [1,2, "hello", 3, 4]

- 삭제 ( pop(), popleft() )

q = deque([1,2,3,4])
q.popleft() #[2,3,4] 1삭제
q.pop()		#[2,3] 4삭제
print(q)

결과는 다음과 같다.

---

BFS 알고리즘에 대해 정리해보자.
BFS개념은 아는데 막상 코드를 짜라고 하면 짜지 못한다..

0번 노드에서 시작해보자.
0을 큐에 삽입하자. 방문했으니 방문처리도 해주자. (visited = Trie)
이후 반복문에서 삭제해주면서 인접 노드를 방문해주면 될 것이다.

위에서 말한 것처럼, 0을 큐에서 삭제(popleft)해준다.
삭제한 요소와 인접한 노드를 반복문을 통해 살펴보자.
0과 인접한 노드는 1,2,4이다.
1,2,4 요소를 탐색하며 방문하지 않았다면, (방문노드가 False)
q.append해주자! q에 넣어주고, 방문처리해주자!

그럼 이렇게 될 것이다.
이제 다시 돌아와서 1을 popleft()하면서, 1을 now로 설정해준다.

1과 인접한 노드 && 방문하지 않은 노드 = ?
1과 인접한 노드는 0과 2이지만, 0은 이미 방문처리가 되었다. 그렇다면

1과 인접한 노드 && 방문하지 않은 노드 = 2이다.
다시 2를 방문하자



위 과정을 하다보면,

모든 노드를 인접한 노드 순으로 탐색하게 되며, 방문처리한 노드를 pop해주면서 큐가 비게 된다.
큐가 비워지면, 모든 노드를 탐색했다는 뜻이다!

def bfs(graph, start, visited_bfs):
  q = deque( [start] )
  visited_bfs[start] = True
  while q:
    now = q.popleft()
    print(now,end=' ')
    for i in graph[now]:
      if visited_bfs[i] == False:
        q.append(i)
        visited_bfs[i] = True

코드는 다음과 같다.

시작점을 deque에 넣어주고, 방문처리해주었다.

이후 덱이 빌 때까지 인접 리스트를 모두 돌고 방문처리 + 덱에 추가 해주면 된다.

위 알고리즘으로 코드를 작성하면 된다.