0-1 BFS는 기본적으로 BFS와 동일하지만 간선의 이동 비용이 0과 1인 경우를 이야기한다. 때문에 적은 비용으로 이동하기 위해서는 비용이 0인 간선으로 이동하는 것을 최대한 장려해야한다.
0-1 bfs는 덱을 사용하여 구현할 수 있다. 지금까지 스택, 큐는 자주 사용했지만 덱은 다뤄본 적이 거의 없다.
먼저 덱(deque)은 큐와 비슷하지만 왼쪽과 오른쪽 모두 pop이 가능한 자료구조이다.
알고리즘은 다음과 같다.
1. 현재 덱의 현재 노드를 꺼내본다.
2. 인접노드를 살펴본다.
3. 인접노드로 넘어가는데 비용이 0이면 front에 1이면 back에 삽입한다. -> why?
왜 프론트와 백에 따로 저장을 할까? 이것은 본문 두번째 줄의 비용이 0인 간선 이동을 장려해야하기 때문이다. 2*x 는 비용이 0이니까 프론트로 보내 우선적으로 계산하고 비용이 드는 정보는 나중에 체크해보는 아이디어이다. 이는 0혹은 1이라는 특수상황에 매우 유용하게 사용할 수 있다.
deque의 함수
push_back()
push_front()
pop_back()
pop_front()
empty()
size()
백준에서 입문 문제로는
https://www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
이 문제가 대표적이다. 코드는 다음 포스팅에
'CS > 자료구조,알고리즘' 카테고리의 다른 글
| 문자열 관리 자료구조 - 트라이(Trie) 개념/구현 (0) | 2023.02.24 |
|---|---|
| DFS를 활용한 순열 (0) | 2023.02.23 |
| 유클리드 호제법(Euclidean algorithm) - 최대공약수, 최소공배수 알고리즘 (0) | 2023.02.22 |
| DFS를 활용한 조합 (1) | 2023.02.14 |
| 그래프 이론 - 깊이 우선 탐색: DFS (1) | 2022.08.27 |
