[프로그래머스] / [Level 2] / [Python] 숫자 변환하기

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

프로그래머스

---

BFS를 활용하여 해결하였습니다.

append 하는 부분에서 이전에 확인했던 값이 들어있는 경우가 많아 check 배열을 만들어 확인하지 않은 숫자들만 append를 진행하도록 하였습니다.

애초에 arr을 set으로 설정하고 풀이해도 괜찮을 것 같습니다.

from collections import deque

def solution(x, y, n):
    if x == y: return 0
    answer = 0
    
    arr = deque([x])
    check = [0] * 1000001
        
    while True:
        answer += 1

        for _ in range(len(arr)):
            num = arr.popleft()
            
            first = num + n
            second = num * 2
            third = num * 3
            
            if first == y or second == y or third == y:
                return answer
            else:
                if first < y and check[first] == 0:
                    arr.append(first)
                    check[first] = 1
                if second < y and check[second] == 0:
                    arr.append(second)
                    check[second] = 1
                if third < y and check[third] == 0:
                    arr.append(third)
                    check[third] = 1
        
        if len(arr) == 0:
            return -1