문제링크 : https://www.acmicpc.net/problem/14562
from collections import deque
c = int(input())
for i in range(c):
s,t = map(int,input().split())
def a(s,t):
return 2*s, t+3
def b(s,t):
return s+1, t
bfs = deque()
bfs.append((s,t,0))
result=0
while bfs:
chk = bfs.popleft()
if chk[0]==chk[1]:
result=chk[2]
break
elif chk[0]>chk[1]:
pass
else:
bfs.append((chk[0]*2, chk[1]+3 , chk[2]+1))
bfs.append((chk[0]+1, chk[1] , chk[2]+1))
print(result)
이 문제는 BFS를 활용해 탐색을 하다 조건을 만족하면 탐색을 마치고 값을 반환하는 풀이를 이용한다. 문제에서 A킥과 B킥을 잘 사용해서 최소 횟수로 조건을 만족시키라고 했다. 이때 너무 많은 경우의 수가 존재하고 이를 하나씩 확인하는 수 밖에 없다고 판단했다. 즉 완전탐색(브루트포스)의 한 종류인 BFS를 이용해 문제를 풀이했다.
=> BFS 핵심 키워드 : 큐 구조