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

문제

자연수 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

---

입출력 예

x y n result

10	40	5	2
10	40	30	1
2	5	4	-1

---

입출력 예 설명

입출력 예 #1

x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2

x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3

x를 y로 변환할 수 없기 때문에 -1을 return합니다.

풀이

 핵심 아이디어

• 각 계산 결과값을 가지고 y값에 가까워지는지 dfs로 탐색하면 된다. </aside>

코드

from collections import deque

def solution(x, y, n):
    answer = 0
    # dfs/bfs로 최소 연산 찾기
    visited=[0 for _ in range(y+1)]

    def dfs(x,y,n):
        minimum = int(1e9)
        queue = deque([])
        queue.append([x,0])
        visited[x] = 1
        while queue:
            t, cnt = queue.popleft()
            if t == y:
                if cnt < minimum:
                    minimum = cnt
            a,b,c = t+n,t*2, t*3
            if x<= a <=y and not visited[a]:
                visited[a] = 1
                queue.append([a, cnt+1])
            if x<= b <=y and not visited[b]:
                visited[b] = 1
                queue.append([b, cnt+1])
            if x<= c <=y and not visited[c]:
                visited[c] = 1
                queue.append([c, cnt+1])  
        return minimum
    answer = dfs(x,y,n)
    if answer == int(1e9):
        return -1
    return answer