백준 1914번 파이썬 코드

문제

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

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

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

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

입력

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

 

 

문제풀이

이 문제는 N이 100까지 간다. 즉, 일반적인 재귀 함수로 하노이의 탑을 100회까지 푼다고 생각을 하면 못 풀겠구나라는 생각이 들었다. 왜냐하면, 이거보다 쉬운 하노이의 탑 문제도 엄청난 시간을 잡아먹었기 때문에... 따라서, 일반적인 재귀로 풀 수 없다는 생각이 들어 먼저 규칙을 찾았다. 

N = 4일 때, 아래와 같은 표의 규칙으로 움직인다.
1~4번 블록은 모두 1이라는 위치에서 시작하는데, 1번 블록은 1->2->3->1->2->3.. 순으로 움직인다. 2번 블록은 반대인 1->3->2->1->3 순으로 움직인다. 그리고 그 시행횟수는 각각 2**n을 따르는 것을 확인했다. 즉, N = K인 하노이의 탑의 합은 다음과 같이 표현할 수 있다.

전체 이동횟수 = 2**0 + 2**1 + .... + 2**n

열: 시행횟수 행 : 각 블록	1	2	3	4	5	6	7	8	TOTAL
1	2	3	1	2	3	1	2	3	8(2**3)
2	3	2	1	3					4(2**2)
3	2	3							2(2**1)
4	3								1(2**0)

그렇다면 이동순서는 각각 어떻게 되는 걸까? N이 4인 경우는 아래와 같은 순서로 움직인다

1,2,1,3,1,2,1,4,1,2,1,3,1,2,1

즉, 2번이 한번 움직일 때 1번이 앞뒤로 각각 1번번 움직이고, 3번이 한번 움직일 때, 2번이 앞뒤로 각각 1번 움직인다. 그렇다면 재귀함수에서는 다음과 같이 표현을 할 수 있다.

def hanoi(층)
  hanoi(아랫층)
  hanoi(현재층)
  hanoi(아래층)

위와 같은 두 가지 사실을 감안하고, N이 20보다 같거나 작을 때까지만 동작하게 한다면 아래와 같은 코드가 만들어진다. 또한, 재귀 제한은 충분히 풀어주어야 하는데, 그 이유는 N=20일 때, 재귀 동작이 총 1,048,575 되기 때문이다.

 

import sys
sys.setrecursionlimit(10000000)

def sol(lv,rotate) :
    if lv == 1 :
        if rotate == 1 :
            nextt_idx = d[1] + rotate
            if nextt_idx > 3 :
                nextt_idx = 1

        else :
            nextt_idx = d[1] + rotate
            if nextt_idx < 1 :
                nextt_idx = 3
        print(d[1], nextt_idx)
        d[1] = nextt_idx

        return
    else :

        sol(lv-1, (-1)* rotate)
        if rotate == 1 :
            nextt_idx = d[lv] + rotate
            if nextt_idx > 3 :
                nextt_idx = 1
        else:
            nextt_idx = d[lv] + rotate
            if nextt_idx < 1:
                nextt_idx = 3
        print(d[lv], nextt_idx)
        d[lv] = nextt_idx
        sol(lv - 1, (-1) * rotate)

n = int(sys.stdin.readline().rstrip())
d = [ 1 for _ in range(21)]
my_sum = 0
for i in range(0,n) :
    my_sum += 2**i

print(my_sum)
if n <= 20 :
    sol(n,-1)