[DFS/BFS] 프로그래머스 level 2 숫자 변환하기 (Python 파이썬)

💡문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/154538?language=python3#

프로그래머스

 

💡문제 분석 요약

자연수 x를 자연수 y로 변환하는 문제. 변환하는 방법은 단 세가지이다. 참고로 n은 y보다 작은 자연수이다.

1. x + n

2. x * 2

3. x * 3

자연수 x, y, n에 대해 x를 y로 변환하기 필요한 최소 연산 횟수를 반환하는 문제

 

💡알고리즘 설계

모든 가능한 경우의 수를 단계별로 탐색하는 BFS를 이용한다. 가장 먼저 도달한 경로가 최소 변환 횟수를 보장한다.큐에는 (ㅣ, c)가 원소로 들어간다. l : 현재 위치. 초기에는 자연수 xc : 현재 위치에 오기까지 변환 횟수. 초기에는 0

 

💡코드

from collections import deque

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

 

💡 오답 풀이

처음에 변수 n을 중복해서 틀렸다. 그래서 두번째 n을 nn으로 바꿨다.

 

💡 느낀점 or 기억할정보