[백준] 11729 파이썬(python) : 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

 

*설명을 위해 앞자리 숫자로 번호추가

1 def hanoi_tower(n, start, to, end):
2    if n == 1:
3        print(start, end)
4    else:
5        hanoi_tower(n-1, start, end, to) #1
6        print(start, end) #2
7        hanoi_tower(n-1, to, start, end) #3
8 n = int(input())
9 print(2**n-1)
10 hanoi_tower(n, 1, 2, 3)

 

하노이 탑 문제다. 사실 아직도 정확하게 이해가 되지는 않는다. 하지만 언젠가 재귀문제를 슉슉 풀 수 있게 되길 소망하면서 포스팅해보겠다. 

 

하노이 타워는 start, to, end 3가지 장대에 있는 원판을 start에서 end로 옮기는 게임이다.

규칙은 다음과 같다.

 

1. start장대에 있는 위에서부터 n-1개의 원판을 end장대를 거쳐서 to장대에 옮긴다.

2. start장대에 있는 마지막 원판을 end장대로 옮긴다.

3. to장대에 있는 n-1개의 원판을 start장대를 거쳐 end장대로 옮긴다.

 

코드에서 보여지는 재귀함수를 따라 과정을 수월하게 풀어낼 수 있다.

#1 : start에서 end를 거쳐 tofh

#2 : start에 있는 마지막 원판을 end장대로

#3 : to장대에 있는 n-1개의 원판을 end장대로

 

 

진행과정을 적어보았다.

(n, 1, 2, 3) n = 3
(2, 1, 3, 2) n = 2
(1, 1, 2, 3) n = 1
*(1, 3) n = 1 if문
*(1, 2) n = 2 6줄
(1, 3, 1, 2) n = 1 7줄
*(3, 2) n = 1 if문
*(1, 3) n = 3 6줄
(2, 2, 1, 3) 7줄
(1, 2, 3, 1) 5줄
*(2, 1) n = 1 if문
*(2, 3) n = 2 6줄
(1, 1, 2, 3) 7줄
*(1, 3) n = 1 if문