하노이의 탑 (Python)

컴퓨터공학과 1학년이라면 누구나 이 탑을 만나봤을 것이다.

1학년 때 알코올로 뇌를 적셔서 기억이 하나도 없는 관계로 이 포스팅을 계기로 한번 정리해보고자한다.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

1. 한번에 하나의 원판만 옮길 수 있다.

2. 큰 원판이 작은 원판 위에 있어서는 안된다.

 이 그림을 보면 쉽게 이해할 수 있다. 이 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 일반적으로 원판이 n개 일 때, 번의 이동으로 원판을 모두 옮길 수 있다.  

자, 그럼 어떻게 옮겨야할까?

                  

 

문제를 유심히 보면 다음 과정이 반복되는 것을 알아챌 수 있다.

1. A에 있는 n-1개의 원판을 C를 이용해서 B로 옮긴다.

2. 가장 큰 원판을 C로 옮긴다.

3. B에 있는 n-1개의 원판을 A를 이용해서 C로 옮긴다.

이를 코드로 작성해보면 아래와 같다.

 

def hanoi(n, _from, _to, _by) :
    if n == 1 :
      print(_from, "->", _to)
      return
    hanoi(n-1, _from, _by, _to)
    print(_from, "->", _to)
    hanoi(n-1, _by, _to, _from)

출처 : 위키백과 하노이의 탑 https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91