[프로그래머스 Lv.2] 숫자 변환하기 (Python)

👩🏻‍💻

DFS 아니면 DP로 풀어야할 것 같다는 생각은 들었다.
for num in [tmp + n, tmp * 2, tmp * 3]
이 반복문과 매우매우 비슷한 코드를 백준 문제에서도 작성한 적이 있다.
근데 코드를 어떻게 시작해야 될지 감이 안잡혀서 다른 분들의 코드를 참고했다.
확실히 DP로 푸신 분들이 많았지만 내 기준 DFS가 더 이해가 잘 되어서 DFS로 풀었다.

큐에 넣어놓고 하나씩 꺼내면서 방문해 주는 방식으로 풀었다.
방문을 이미 한 것은 어차피 큐에 들어가있고 그 과정에서 for문에 돌려질 것이기 때문에 패스해주었다.
visited 함수를 중심으로 풀어나갔으며 결과적으로 연산 횟수를 리턴해야 하기 때문에 visited에 방문한 횟수를 리턴해주었다.

요즘 BFS랑 DFS 문제를 많이 풀었더니 두 풀이의 차이점을 알게 된 것 같다.

코드

from collections import deque

def solution(x, y, n):
    visited = [0] * (y + 1)
    queue = deque([x])
    
    while queue:
        tmp = queue.popleft()
        if tmp == y:
            return visited[tmp]
        
        for num in [tmp + n, tmp * 2, tmp * 3]:
            if num <= y and not visited[num]:
                queue.append(num)
                visited[num] = visited[tmp] + 1
    
    return -1