[Python] 백준 12852번 1로 만들기 2

12852번: 1로 만들기 2

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

코드

from collections import deque

n = int(input())

def bfs(n):
    q = deque([(n, [n])])
    visited = [False for _ in range(n + 1)]
    visited[n] = True
    
    while q:
        now, arr = q.popleft()
        if now == 1:
            print(len(arr)-1)
            for i in arr:
                print(i, end=" ")
            break
        if now % 3 == 0:
            nx = now // 3
            if not visited[nx]:
                q.append((nx, arr + [nx]))
                visited[nx] = True
        if now % 2 == 0:
            nx = now // 2
            if not visited[nx]:
                q.append((nx, arr + [nx]))
                visited[nx] = True
        nx = now - 1
        if not visited[nx]:
            q.append((nx, arr + [nx]))
            visited[nx] = True
            
bfs(n)

처음에는 Top-down 방식으로 입력받은 n이 1이 될 때까지 탐색하는 방식으로 풀었다. BFS의 동작원리를 생각해보면 1에 가장 먼저 도달하는 것이 가장 최소로 연산하는 방법이라는 것은 어렵지 않게 알 수 있다.

 

이 문제의 풀이에는 다양한 방법이 존재할 것 같아서 다른 사람들은 다른 방식으로 어떻게 풀었나 찾아보니 역시나 다들 다양하게 풀이하고 있었다. DFS, BFS, 다이나믹 프로그래밍 등 여러 가지 풀이가 가능한 것으로 보였다. 그러던 중 내가 푼 BFS도 Bottom-up 방식으로 구현하는게 더 간단하다는 댓글을 보고 코드를 아래와 같이 수정해보았더니 더 보기 좋고 간결해졌다. 

 

from collections import deque

n = int(input())

def bfs(n):
    q = deque([(1, [1])])
    visited = [False for _ in range(n + 1)]
    visited[1] = True
    
    while q:
        now, arr = q.popleft()
        if now == n:    # n에 처음 도달하는 것이 최단 루트
            print(len(arr)-1)
            for i in arr[::-1]:
                print(i, end=" ")
            break
        for nx in [now*3, now*2, now+1]:
            if nx <= n and not visited[nx]:
                q.append((nx, arr + [nx]))
                visited[nx] = True
            
bfs(n)