[python/파이썬] 백준 11729 하노이 탑 이동 순서

[문제 출처]

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

11729번: 하노이 탑 이동 순서

 

[문제 풀이]

하노이 탑은 3개의 장대가 있을 때 첫 번째 장대에서 세 번째 장대로 원판을 모두 옮겨야 한다.

원판은 모두 크기가 다르며 큰 원판 위에 작은 원판을 얹을 수 있다.

이 규칙을 이용해 문제를 풀어보면

 

첫 번째 장대에서 세 번째 장대로 n개의 원판을 옮기기 위해서는 두 번째 장대로 n-1개의 원판을 모두 옮긴 후에

가장 사이즈가 큰 n번째 원판을 세 번째 장대로 옮겨야 한다.

 

두 번째 장대에서 세 번째 장대로 n-1개의 원판을 옮기기 위해서는 첫 번째 장대로 n-2개의 원판을 모두 옮기 후에

가장 사이즈가 큰 n-2번째 원판을 세 번째 장대로 옮겨야 한다.

 

결국 n개를 세 번째로 옮기는 문제는 n-1개를 두 번째로, n-2개를 첫 번째로 옮기는 등의 작은 문제로 나눠질 수 있다.

이를 이용해 재귀 함수를 작성하면 아래의 코드와 같다.

 

n = int(input())

def move(a, b, c , size):
  if size==1:
    print(a,c)
  else:
    move(a, c, b, size-1)
    print(a, c) #??
    move(b, a, c, size-1)

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