[Baekjoon] 11729번 : 하노이 탑 이동 순서 (Python, 재귀)

[Baekjoon] 11729번 : 하노이 탑 이동 순서 (Python, 재귀)

 

목차

 

 

 

 

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 1104ms / 코드 길이 196B

 

하노이 탑의 기둥이 1,2,3이라고 할 때 1 기둥의 원판을 3 기둥에 옮기고 싶은 것이 목적이다.

하노이 탑의 특성상 항상 위에 있는 원판은 아래 있는 원판보다 작은 숫자이어야 한다.

 

고로 다음과 같이 진행한다. (n개 원판이 1번 기둥에 존재한다고 가정)

 

n개 원판	0	0
1번 기둥	2번 기둥	3번 기둥

 

1번 기둥의 n-1 개의 원판을 2번 기둥에 모두 옮긴다고 생각

 

1개 원판	(n-1)개 원판	0
1번 기둥	2번 기둥	3번 기둥

 

0	(n-1)개 원판	1개 원판
1번 기둥	2번 기둥	3번 기둥

 

0	0	n개 원판
1번 기둥	2번 기둥	3번 기둥

 

  

그리고 1번 기둥에 남은 가장 큰 원판을 3번 기둥에 옮긴다.

2번 기둥에 옮긴 n-1개를 3번 기둥에 옮긴다면 1번에서 3번 기둥으로 모든 원판을 옮기는 것이다.

 

이제 재귀적으로 n-1개에 대해 어떻게 옮겨지는지 또 함수 속으로 들어가야한다.

이때 재귀 종료 시점은 n=0이 될 때로 설정한다.

 

 

하노이 탑 총 이동 횟수 구하는 법 $2^n - 1$

 

 

1번 기둥의 n개 원판을 3번 기둥으로 옮긴다고 했을 때

 

$a_n$ : n 개의 원판을 1번에서 3번으로 옮길 때 횟수

$a_{n-1}$ : n-1 개의 원판을 특정 기둥에서 다른 기둥으로 옮길 때의 횟수

 

$a_n = a_{n-1} + 1 + a_{n-1} = 2 a_{n-1} + 1$

$a_n + 1 = 2(a_{n-1} + 1)$

$a_n + 1 = 2^{n-1} (a_1 + 1)$ 이때 $a_1=1$

$$a_n = 2^n - 1$$

 

 

def hanoi(n, src, dst):
    tmp = 6 - src - dst
    if n == 0:
        return
    hanoi(n-1, src, tmp)
    print(src, dst)
    hanoi(n-1, tmp, dst)

n = int(input())
print(2**n - 1)
hanoi(n, 1, 3)