PS: 백준 1463번 - 1로 만들기

https://www.acmicpc.net/problem/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
예제 : 입력 10 -> 출력 3

나의 코드

c = 0
n = int(input())
if n == 1:
    print(0)
    exit()
node = [[n]]
flag = 0
while True:
    node.append([])
    for i in node[c]:
        if i - 1 == 1:
            flag = 1
            break
        else:
            node[c+1].append(i - 1)
        if i % 2 == 0:
            if i / 2 == 1:
                flag = 1
                break
            node[c+1].append(i // 2)
        if i % 3 == 0:
            if i / 3 == 1:
                flag = 1
                break
            node[c+1].append(i // 3)
    c += 1
    if flag == 1:
        break

print(c)

예제처럼 10이 주어지면 가능한 경우는 10-1와 10/2 두가지 일 것이다. 그리고 저 두가지에서 계산된 9와 5는 각각 9-1, 9/3 그리고 5-1로 계산될 수 있을 것이다.
나는 이 과정들을 트리로 표현하고 넓이우선탐색으로 트리를 탐색하여 1이 나오는 최소층을 찾으려 했다.

트리는 이차원 리스트로 표현하였다.

node[row][col]

row는 트리의 각 층을 나타낸다. 0번 인덱스는 0층, 1번 인덱스는 1층과 같다.
그리고 각 row마다 리스트를 통해 해당 층에 있는 노드들을 표현했다.
10을 예시로 한다면

row - [해당 층의 노드들]
0층 - 10
1층 - 9, 5
2층 - 8, 3, 4
3층 - 7, 4, 1, 3, 2

이러한 구조를 통해 1이 등장하는 최소층을 구하려 했다.
그래서 가장 바깥쪽 while 을 통해 층수를 나타내는 변수 c를 하나씩 늘려주며 각 층마다의 노드들을 for문을 통해 탐색하였다. 그리고 각 노드들을 탐색할 때마다 해당 노드들이 가질 수 있는 자식 노드들(가능한 연산 케이스들 ex)2로 나눈 값, 3으로 나눈값)을 다음 층 리스트에 추가하였다.

이때 아쉬운 점은 n이 1인 경우 c가 결과가 0이 아닌 1로 나와서 이 부분은 처음에 따로 n == 1인 경우로 처리해주었다.

백준 채점 결과 걸린 시간은 664ms였다. 시간이 좀 오래 걸린 것 같고 0층부터 모든 층을 다 저장하며 탐색하기 때문에 메모리도 많이 쓰지 않을까 생각한다. 아직까지 채점 전에 내 코의 시간복잡도와 공간복잡도를 예상하는 것이 좀 어렵다.
다른 분들이 푼 코드를 보았는데 시간도 엄청나게 적게 걸리고 접근 방식도 사뭇 달라서 보고 배우려한다. ㅠㅠ