[백준]_12852번 : 1로 만들기 2(파이썬)

728x90

12852번: 1로 만들기 2

1로 만들기 문제에서 업그레이드된 문제이다. 이 문제는 크게 두 가지 영역으로 나뉘고 서로 거의 독립적인 코드를 요구한다. 사실 1번 코드로부터 2번 코드에서 사용될 정보는 1번 코드의 결괏값 1개뿐이다.

1. 이 문제에서 요구하는 그대로 1로 만들기 위해 필요한 연산 횟수를 구하는 코드.
2. 입력 n에 대해 1까지의 경로를 탐색하는 코드. 

1번 코드는 이미 만들었다고 가정하고(궁금하면 위의 링크를 타고 해결책(dp, bfs)을 보고 오시기를 바랍니다) 2번 코드만 작성해 보겠다. 

접근 

 

n에 대한 연산 횟수 정보를 이미 얻었다고 가정하고 이 값을 A라고 하자. 이제 n에서 출발하여 1까지 도달하는 과정을 알아내야 한다. 이것은 깊이 우선 탐색(dfs)으로 구할 수 있어 보인다. 

 

dfs를 재귀로 하기 위해서는 두 가지가 필요하다. 프로그램 탈출 조건(정답을 찾았을 때)은 무엇이고 함수 탈출 조건(그래프에서 현 방향이 오답임을 알았을 때)은 무엇인가 이다.

 

dfs 특성상 append, pop이 일어날 리스트의 상태에 따라 상황이 좌우된다. 우리가 원하는 프로그램 탈출 조건은 

• 리스트의 크기가 A+1(시작 n과 1을 포함해야 되기 때문에 A+1이 정답 리스트의 크기이어야 한다)
• 내림차순으로 대입될 것이므로 리스트의 마지막 원소가 1일 때

위를 모두 만족시킬 때이다.

 

반면에 함수 탈출 조건은

• 리스트의 크기가 A+1까지 채워졌지만 마지막 원소가 1이 아닐 때

이다. 여기서 리스트의 크기가 A+1이 되기도 전에 마지막 원소가 1인 상황이 올 수도 있지 않나고 생각할 수 있지만, 애초에 A+1이 1번 코드에서 구한 최소 경로이기 때문에 정답 리스트의 크기가 A+1보다 작으면서 정답일 수가 없다.

 

최종 코드>>

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())
Q = deque([n])
trace = [0] * (n + 1)
while Q:
    target = Q.popleft()
    if target == 1:
        break
    if target % 2 == 0 and not trace[target // 2]:
        Q.append(target // 2)
        trace[target // 2] = trace[target] + 1
    if target % 3 == 0 and not trace[target // 3]:
        Q.append(target // 3)
        trace[target // 3] = trace[target] + 1
    if not trace[target - 1]:
        Q.append(target - 1)
        trace[target - 1] = trace[target] + 1
print(trace[1])
ans = []
ans.append(n)

def search(size, target):
    if len(ans) == size and ans[-1] == 1:
        print(*ans)
        exit()
    if len(ans) == size and ans[-1] != 1: return
    num = target
    if num % 3 == 0:
        ans.append(num // 3)
        search(size, num // 3)
        ans.pop()
    if num % 2 == 0:
        ans.append(num // 2)
        search(size, num // 2)
        ans.pop()
    ans.append(num - 1)
    search(size, num - 1)
    ans.pop()

search(trace[1] + 1, n)