[알고리즘](파이썬)16953-A→B

문제

 

소스코드

import sys
from collections import deque

n,b = map(int,sys.stdin.readline().split())
q= deque()
q.append([n,1])         #현재 값과 레벨과 넣기

f=0
while(q):
    k=q[0]  
    if(k[0]==b):        #맨 앞에 칸이 b와 같은지 확인
        print(k[1])
        f=1
        break
    else:  
        q.popleft()     #다를 경우 큐에서 빼내고 해당 값에서 파생된 값 갱신
        if(k[0]*2<=b):  #비교하려는 값보다 클 경우에는 넣지 않음
            q.append([k[0]*2,k[1]+1])
        if(k[0]*10+1<=b):
            q.append([k[0]*10+1,k[1]+1])

if(f==0):              #만들 수 없는 경우 -1출력
    print(-1)

 

코멘트

 

bfs구현을 위해 파이썬에 있는 Deque를 사용했습니다.

큐 값으로는 리스트[정숫값,레벨값]을 넣었습니다.

 

정숫값을 비교하고 틀리면 해당 리스트를 큐에서 제거하고 [해당 정숫값에서 파생된 값,해당 레벨값+1]을 큐에 넣어줍니다. 그리고 맞거나 큐가 빌때까지 계속 이 과정을 반복해줍니다.

 

반복 끝에 정숫값이 일치하게 되면 해당 리스트의 레벨값을 출력해줍니다. 결국 못 찾고 반복문을 빠져나오면 -1을 출력합니다.

 

bfs 너비우선 탐색
#깊게 탐색하기 전에 넓게 탐색한다.
#시작 노드에 인접한 노드부터 탐색하는 알고리즘
#사용하는 경우: 최단경로, 임의의 경로 찾기
#방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용(->선입선출)
#재귀적으로는 동작하지 않는다.