[프로그래머스] Lv.2 숫자 변환하기 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/154538
• 🔑 BFS 
  • 6번 테스트 케이스 계속 통과 안 된 이유 🤬
    • x == y 일 때 0번 만에 만들 수 있다.
  • 트리를 defaultdict를 사용해 기본 값을 0으로 둔다.
  • 큐에 x를 넣어놓고 bfs를 진행
  • 현재 큐에 있는 값으로  x + n, x * 2, x * 3을 해본다.
  • y를 넘어가면 건너뛰고
  • 아니면 계산된 수에 현재 깊이 +1을 한다.
  • 계산된 수를 큐에 넣는다.
  • bfs 종료 후 tree[y]의 값을 리턴한다. (0이면 -1 리턴)

 

from collections import defaultdict, deque

def solution(x, y, n):
    
    if x == y: return 0
    
    tree = defaultdict(int)
    q = deque([x])
    
    while q:
        num = q.popleft()
        
        for next_num in [num + n, num * 2, num * 3]:
            if next_num > y:
                continue
            else:
                if tree[next_num] == 0:
                    tree[next_num] = tree[num] + 1
                    q.append(next_num)

    return tree[y] if tree[y] else -1