[파이썬] 백준 알고리즘 No.14562 태권왕

백준 14562번 태권왕 문제

 

 

127572kb, 148ms

 

 

from collections import deque

def bfs(s, t):
    queue = deque()
    queue.append((s, t, 0))
    visited = [-1] * (200)

    while queue:
        s, t, count = queue.popleft()
        if s <= t and visited[s] == -1:
            queue.append((s * 2, t + 3, count + 1))
            queue.append((s + 1, t, count + 1))
            if s == t:
                return count


c = int(input())
for i in range(c):
    s, t = map(int, input().split())
    print(bfs(s, t))

 

bfs를 통해 풀 수 있는 문제.
매 분기마다 A의 발차기를 할지, B의 발차기를 할지
모든 분기를 저장하여 가장 빠른 s == t에 도달한 count를 출력하면 끝.