# 0-1bfs

mj3242

문제 https://www.acmicpc.net/problem/14497 리뷰 다익스트라 또는 0-1 BFS로 풀이할 수 있는 문제였다. 다익스트라의 경우 dist 를 $N \times M$ 2차원 배열의 형태로 정의한뒤 시작점을 0, 도착점을 1로 비용 설정해주어 map의 값에 따라 다익스트라 로직을 진행해주면 도착점까지의 최소 비용을 dist 값을 통해 구할 수 있다. 0-1 BFS의 경우 덱을 이용하여 비용이 없는(0) 경로가 우선시 되어 탐색될 수 있도록 offerFirst 해주며 도착점에 도달하였을 시 비용을 반환해주는 방식으로 구성하였다. 시간복잡도 다익스트라 로직의 시간복잡도는 $O(ElogV)$ 로 수렴하는데 $E=4 \times N \times M$, $V=N \times M$ 이고 0-1 BFS 로직의 경우 $O(N \times M)$의 복잡도를 띈다. 두 로직 모두 $N=M=500$인 최악의 경우에도 무난히 2

www-jong

문제 : https://www.acmicpc.net/problem/13549 풀이 일반적인 bfs가 아닌 0-1를 이용하는 문제이다. 0-1 bfs는 아래과정과 같이 진행된다 deque의 front(left)에서 현재노드를 꺼냄 연결된 인접 노드 탐색 해당 인접노드를 탐색할 수 있을 경우(이동가능한 경우) 해당 노드를 향하는 가중치가 0이면 덱의 front(left)에 삽입 해당 노드를 향하는 가중치가 1이면 덱의 back에 삽입 가중치가 가장 낮은 정점으로의 이동을 우선순위로 해야하므로 덱의 front에 삽입하게 된다. 일반 bfs와 동일하게 간선의 갯수(E)만큼 탐색, 정점의 갯수(V)만큼 중복없이 방문하므로 시간복잡도는 O(V+E)로 동일하다.

y7y1h13

처음에 시간이 다 1이 느는줄 알았다... 하지만 나중에 보니 순간이동은 시간이 늘지 않았다. 가중치가 0, 1로 이루어져 있으면 0-1bfs를 사용하면 된다. 만약 가중치가 여러개면 다익스트라를 사용 가중치가 0인 계산이 들어오면 appendleft를 이용해서 큐 맨 앞에 추가시켜 준다. 참고