Baekjoon 1463번 1로 만들기

💭 문제가 궁금하다면?

내가 시도한 방법

아래 그림은 위 문제를 상태 트리로 나타낸 것이다.
처음에 어떻게 풀지 감이 오지 않았었는데, 그림으로 하나씩 풀어내면서 bfs를 사용할 수 있겠는데? 라는 생각이 들었다.

from collections import deque

# 주석 처리된 q는 deque를 사용하지 않고, list의 pop 메소드 사용
# queue는 deque를 import해서 사용

def bfs(start):

    # q = [start]
    queue = deque()
    queue.append(start)
    visited = [0]*(10**6+1)
    visited[start] = 1

    while queue:
        # current = q.pop(0)
        current = queue.popleft()
        
        if current == 1:
            return visited[current] - 1

        for new, check in [(current // 3, current % 3), (current // 2, current % 2), (current - 1, 0)]:
        	# (현재 - 1)은 무조건 q에 추가되고, 2나 3으로 나누어떨어질 때 q에 추가
            if not check and not visited[new]: 
                # q.append(new)
                queue.append(new)
                visited[new] = visited[current] + 1


number = int(input())
print(bfs(number))

후기

• pop(0)는 배열을 재배치해야하기 때문에 시간이 오래걸린다고 생각했지만, 실질적으로 deque보다 더 적게 들었다.(엄청난 차이는 아니였지만)
• 교수님이 deque를 쓰는게 무조건 빨라지는 게 아니라고 말씀하셨던 게 생각났다.