0-1 BFS
0-1 BFS란 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾는 알고리즘이다.
최단 경로는 다익스트라가 최고 아님?
보편적인 다익스트라의 시간복잡도는 O(ElogE) 혹은 O(ElogV)이다.
하지만 0-1 BFS의 시간복잡도는 O(V + E)이다.
0-1 BFS의 동작방식
- deque front에서
노드(now)pop 인접 노드(next)를 체크한다.현재 노드(now)까지의 비용 + 인접 노드(next)로의 가중치<인접 노드(next)까지 소요된 최적의 비용인 경우 next까지 소요된 최적의 비용을 갱신한다. (<= 가 아니라 < 이다)- next로의 가중치가 0이면 deque front에 삽입, 1이면 deque back에 삽입한다.
- deque가 empty될 때까지 반복
👉 가중치가 0이면 front에 1이면 back에 삽입
숨바꼭질 3
from collections import deque
n, k = map(int, input().split())
inf = float('inf')
gap = abs(n - k) + 2
visited = [inf for _ in range(n + k + gap)]
visited[n] = 0
def bfs():
q = deque([[n, 0]])
while q:
x, count = q.popleft()
if x == k:
return count
if 0 <= 2 * x < n + k + gap:
if visited[2 * x] > count:
visited[2 * x] = count
# 가중치가 0인 경우 deque 의 가장 앞에 삽입한다.
q.appendleft([2 * x, count])
for xx in [x + 1, x - 1]:
if 0 <= xx < n + k + gap:
if visited[xx] > count + 1:
visited[xx] = count + 1
q.append([xx, count + 1])
print(bfs())