[프로그래머스] lv.2 숫자 변환하기 python

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

프로그래머스

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

x에 n을 더합니다
x에 2를 곱합니다.
x에 3을 곱합니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한 사항

1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y

 

문제 풀이

완전 탐색을 이용했다..

완전 탐색은 해도해도 안익숙해지는 느낌

 

먼저 방문확인할 visit리스트를 만들어준다

그리고 x+n, x*2, x*3마다 방문확인을 찍어주는데, 여기서 방문확인에 들어갈 숫자는 연산 횟수이다.

 

x가 y에 갔을 때 visit[x]의 값을 리턴해주면 된다.

만약 리턴안되고 다 돌았다면 -> -1리턴

 

from collections import deque

def solution(x, y, n):
    q=deque()
    q.append(x)
    visit=[0]*(10**6+1)
    while q:
        x=q.popleft()
        if x==y:
            return visit[x]
        for nx in(x+n, x*2, x*3):
            if 0<= nx <= y and not visit[nx]:
                visit[nx]=visit[x]+1
                q.append(nx)
    return -1