문제 : 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)로 동일하다.
from collections import deque
n,k=map(int,input().split())
dis=[0]*100001
q=deque()
q.append(n)
while q:
x=q.popleft()
if x==k:
print(dis[x])
break
for i in (x-1,x+1,x*2):
if 0<=i<=100000 and not dis[i]:
if i!=0 and i==x*2:
dis[i]=dis[x]
q.appendleft(i)
else:
dis[i]=dis[x]+1
q.append(i)
뉴비