S3 1463. 1로 만들기

문제 보기 :  1463번: 1로 만들기

---

문제

• 정답률 : 33%

---

작성 코드

from collections import deque

def find1(n):

    visited = [-1]*(n+1)
    visited[n] = 0

    dd = deque([n])
    while dd:
        now = dd.popleft()

        can = []
        if now % 3 ==0:
            can.append(now//3)
        if now%2 == 0:
            can.append(now//2)
        can.append(now-1)

        for value in can:
            if visited[value]== -1:
                visited[value] = visited[now]+1
                dd.append(value)
                if value == 1:
                    return visited[value]

    return visited[1]

n = int(input())
print(find1(n))

---

풀이

bfs 알고리즘으로 해결했고 visited는 최단경로 문제를 해결할 때 사용하는 [-1]*(n+1)로 두었다. 

그렇게 어려웠던 부분은 없었다!