[Python] 숫자 변환하기

문제

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

프로그래머스

 

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수 작성 (x를 y로 만들 수 없다면 -1 return).

# 사용 가능한 연산
x + n
x * 2
x * 3

# 제한 사항
1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y

• 각 연산은 혼합해서 사용 가능

 

풀이

• 각 연산의 가중치(연산 횟수)는 1로 동일
• 최소 연산횟수 = 최단 거리 탐색 = bfs(너비 우선 탐색) 알고리즘 사용

from collections import deque

def solution(x, y, n):
    if x == y:
        return 0
    
    q = deque() # bfs이므로 큐 사용
    q.append((x, 0)) # 현재값, 현재횟수
    visited = set([x]) # 재탐색 방지용
    
    while q:
        cur, cnt = q.popleft()
        
        for nxt in (cur+n, cur*2, cur*3):
            if nxt == y:
                return cnt + 1
            
            if nxt < y and nxt not in visited:
                visited.add(nxt)
                # 탐색된 순서대로 큐에 저장
                q.append((nxt, cnt + 1))

    return -1