[알고리즘] 0-1 너비 우선 탐색

• 0-1 BFS란?

• BFS는 BFS인데 특수한 환경에서 작동할 수 있는 BFS를 0-1 BFS라고 한다.
• 0-1 BFS는 가중치가 0과 1로만 이루어진 그래프에서 최단 경로를 찾고자 할 때 주로 사용된다.

• 0-1 BFS의 동작 과정

1. deque(덱)의 앞에서 popleft를 통해서 현재 노드를 꺼낸다.
2. 연결된 인접 노드를 살핀다.
3. 현재 노드까지 소비된 비용 + 그 노드로 향하는 간선의 가중치 < 그 노드까지 가는데 소비된 비용
   → 위 식이 성립하면 비용을 갱신해준다.
4. 노드가 갱신된 상태에서 만약 그 노드를 향하는 가중치가 0이면 덱의 front에 삽입appendleft, 가중치가 1이면 덱의 back에 삽입append한다.