BFS (1) 썸네일형 리스트형 0-1 BFS 너비 우선 탐색 0-1 BFS는 기본적으로 BFS와 동일하지만 간선의 이동 비용이 0과 1인 경우를 이야기한다. 때문에 적은 비용으로 이동하기 위해서는 비용이 0인 간선으로 이동하는 것을 최대한 장려해야한다. 0-1 bfs는 덱을 사용하여 구현할 수 있다. 지금까지 스택, 큐는 자주 사용했지만 덱은 다뤄본 적이 거의 없다. 먼저 덱(deque)은 큐와 비슷하지만 왼쪽과 오른쪽 모두 pop이 가능한 자료구조이다. 알고리즘은 다음과 같다. 1. 현재 덱의 현재 노드를 꺼내본다. 2. 인접노드를 살펴본다. 3. 인접노드로 넘어가는데 비용이 0이면 front에 1이면 back에 삽입한다. -> why? 왜 프론트와 백에 따로 저장을 할까? 이것은 본문 두번째 줄의 비용이 0인 간선 이동을 장려해야하기 때문이다. 2*x 는 비용.. 이전 1 다음