태권왕

문제링크 : 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 핵심 키워드 : 큐 구조