BFS는 BFS인데 0-1 BFS는 무엇이냐?
가중치가 0과 1로만 주어진 그래프에서 최단경로를 찾을 때 사용할 수 있는 BFS 응용 알고리즘이다.
그래프에 가중치가 0과 1만 있을때는 다익스트라보다도 0-1 BFS가 더 효율적이다.
그냥 BFS에서는 큐(queue)를 사용하지만, 0-1 BFS에서는 덱(deque)을 사용한다.
현재 노드까지 오는데 소비된 비용 + 다음 노드를 향하는 가중치
가 다음 노드까지 가는데 소비된 비용
보다 작다면, 다음 노드까지 가는데 소비된 비용
을 갱신한다.다음 노드를 향하는 가중치
가 0이면 다음 노드를 deque의 front에, 1이면 back에 삽입한다.파이썬에서는 deque
라이브러리를 사용해 가중치가 0이면 appendleft()
로, 1이면 append()
로 덱에 넣으면 된다.
from collections import deque
N, K = map(int, input().split())
queue = deque([(N, 0)])
visited = [False] * 100001
visited[N] = True
while queue:
now, time = queue.popleft()
if now == K:
print(time)
break
for next, second in [(now*2, time), (now-1, time+1), (now+1, time+1)]:
if 0 <= next <= 100000 and visited[next] == False:
queue.append((next, second))
visited[next] = True
나는 0-1 BFS라는게 따로 있는 줄 모르고 그냥 BFS로 풀었는데 처음엔 틀렸다가 큐에 넣는 부분에서 순서를 [(now-1, time+1), (now+1, time+1), (now*2, time)]
에서 [(now*2, time), (now-1, time+1), (now+1, time+1)]
으로 바꾸니까 맞았다.
0-1 BFS를 사용해서 풀면 다음과 같다.
from collections import deque
N, K = map(int, input().split())
dq = deque([N])
time = [-1] * 100001
time[N] = 0
while dq:
now = dq.popleft()
if now == K:
print(time[now])
break
for next in [now-1, now+1, 2*now]:
if 0 <= next <= 100000 and time[next] == -1:
if next == 2*now:
time[next] = time[now]
dq.appendleft(next) # 이부분이 포인트
else:
time[next] = time[now] + 1
dq.append(next)