[프로그래머스] 숫자 변환하기 (Python)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

풀이

BFS로 풀면 됨.

다만 6번 테스트 케이스에서 계속 틀림

y가 x값과 같을 수 있음을 고려하지못함

if x == y : return 0 추가

 

소스코드

from collections import deque

def solution(x, y, n):
    INF = 1e9
    dp = [INF] * (y+1)
    
    q = deque()
    q.append((x, 0))
    
    while q:
        num, cnt = q.popleft()
        for next_num in (num+n, num*2, num*3):
            if next_num > y:
                continue
            if dp[next_num] == INF:
                dp[next_num] = cnt + 1
                q.append((next_num, cnt + 1))
    
    if x == y: 
        return 0
    elif dp[y] == INF:
        return -1
    else: 
        return dp[y]