11729(하노이 탑 이동 순서) - 해결

하노이 탑 이동 순서

 

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.

쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

 

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

 

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

---

재귀를 좀더 보고싶어서 선택하였는데 재귀를 적게해서 하노이를 어떻게 풀 수 있을까...

계속 터진다... 횟수 자체가 100만이 넘는데 이걸 할 수 있는건가?

def move(a,b,cnt,sticks):
    print("#333",a,b,cnt)
    
    print(sticks)
    global mincnt

    sticks[b].append(sticks[a].pop())
    print("ssss",sticks)
    if len(sticks[3]) == N:
        print("aa",sticks,cnt)
        if mincnt > cnt + 1:
            mincnt = cnt + 1
        return
    for i in range(1,4):
        for j in range(1,4):
            if i == j or i == b:
                continue
            if sticks[i] == []:
                continue
            if sticks[j] == []:
                pass
            elif sticks[j][-1] < sticks[i][-1]:
                continue
            if cnt + 1 > mincnt:
                continue
            print(i,j)
            sts = deepcopy(sticks)
            move(i,j,cnt+1,sts)

역시 내가 생각한 방법대로 하면 될리가 없지... 이런 방식으로 재귀는 힘들지...

import sys
N = int(sys.stdin.readline())

# N개의 탑을 x에서 y로 이동
def move(N,x,y):
    # 1개면 바로 이동
    if N == 1:
        print(x,y)
        return
    # N개를 이동하기위해서는 그 위의 N-1을 다른 곳으로 이동
    move(N-1,x,6-x-y)
    # 맨 밑의 탑을 y로 이동
    move(1,x,y)
    # 아까 옮겼던 N-1를 y로 이동
    move(N-1,6-x-y,y)

# 총 횟수는 전의 횟수 x 2에 + 1
sum = 1
for i in range(N - 1):
    sum = sum * 2 + 1
# 총 횟수
print(sum)
move(N,1,3)