[백준] 11729번 : 하노이 탑 (파이썬)

문제

나의 답안

n=int(input())
def hanoi(num,start,mid,end):
    
    if num==1:
        print(start,end)

    else:
        hanoi(num-1,start,end,mid)	#가장 아래에 있는 원판 제외 나머지 2로 이동(1->2)
        print(start,end)	#처음 장대에 남은 마지막 원판을 3으로(1->3)
        hanoi(num-1,mid,start,end)	#2번째 장대에 있는 다른 원판을 3으로(2->3)

print(2**n-1)
hanoi(n,1,2,3)

접근방법

• 하노이탑 알고리즘, 재귀 문제이다.
• 장대는 총 3개이고, 모든 원판을 첫번째에서 마지막으로 옮기면 된다.
• 따라서 3단계로 나뉜다
  • 1) 첫번째 장대에서 가장 아래에 있는 원판을 제외하고 나머지(n-1개)를 2번째로 이동시킨다.
  • 2) 이후 첫번째 장대에서 가장 아래에 있는 원판을 마지막으로 이동시킨다.
  • 3) 마지막으로 2번째 장대에 있는 다른 원판을 마지막으로 이동시킨다.
• 이를 그림으로 나타내면 다음과 같다.(n==3)
  

코드

1. 하노이 재귀 함수를 정의한다. (def hanoi) 함수의 인자로는 원판의 수(num) 시작 위치(start), 중간 위치(mid), 목표 위치(end)가 있어야 한다.
2. 원판의 수가 1개이면 첫번째에서 마지막으로 이동시키기만 하면 되므로 시작위치와 마지막 위치를 출력해준다.
3. 아니라면, 위의 3단계를 표현해준다.
   hanoi(num-1,start,end,mid) 로 n을 제외한 나머지를 시작위치에서 중간 위치인 mid로 이동시킨다.
   print(start,end) 으로 첫번째 장대에 남아있는 한개의 원판을 마지막으로 이동시킨다.
   마지막으로 hanoi(num-1,mid,start,end)으로 두번째 장대에 있는 n-1 개의 원판을 마지막 장대로 이동시켜준다.
4. 마지막으로 이동횟수를 출력해주고, 함수를 호출한다.

하노이 탑 이동횟수

이동 횟수는 좋은 포스팅을 발견해 해당 글을 참고했다. :)