백준 1463번 1로 만들기

문제는 dp알고리즘으로 되어있지만 최소값을 구하는 문제여서 bfs를 통해서 문제를 풀었다

from collections import deque
import sys
input = sys.stdin.readline
MAX = 10**6+1

n = int(input())
# 연산 3개
# 3으로 나누기 나누어 떨어진다면
# 2로 나누기 나누어 떨어진다면
# -1
# 세가지 연산으로 1만들기
#최솟값 구하기니까 bfs이용?
q = deque()
line = [0 for _ in range(MAX)]

q.append(n)
while q:
    a = q.popleft()
    
    if a == 1:
        print(line[1])
        break

    if a%3 == 0 and a/3 != 0:
        x=int(a/3)
        if line[x] != 0 and line[x]>line[a] + 1:
            q.append(x)
            line[x] = line[a] + 1
        elif line[x] == 0:
            q.append(x)
            line[x] = line[a] + 1

    if a%2 == 0 and a/2 != 0:
        y = int(a/2)
        if line[y] != 0 and line[y]>line[a] + 1:
            q.append(y)
            line[y] = line[a] + 1
        elif line[y] == 0:
            q.append(y)
            line[y] = line[a] + 1


    if line[a-1] != 0 and line[a-1] > line[a] + 1:
        q.append(a-1)
        line[a-1] = line[a] + 1
    elif line[a-1] == 0:
        q.append(a-1)
        line[a-1] = line[a] + 1

bfs로 풀었는데 dp방법이 더 깔끔하게 풀릴것 같다