[Algorithms] 하노이의 탑(Tower of Hanoi)

깃허브: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/hanoi.ipynb

하노이의 탑(Tower of Hanoi)

하노이의 탑(Tower of Hanoi)는 위 그림과 같이 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원반들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원반들이 위에 순서대로 쌓여 있다. 그리고 이동 시킬 때 아래의 두 가지 조건을 만족시키면서 이동 시켜야 한다.

1) 한 번에 하나의 원반만을 옮길 수 있다.

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

 

이러한 하노이의 탑을 해결하는 데 있어서 가장 기초적인 아이디어는 재귀(recursion)이다.

 

먼저 예를 통해 어떻게 풀어야 할지 감을 잡아보자.

1. 원반이 하나인 경우(n=1)

원반이 하나인 경우, 즉 n=1 인 경우에는 시작 기둥에서 목표 기둥까지 1번만 움직이면 된다.

재귀에서는 탈출 조건이 반드시 필요한데, n=1인 경우가 바로 이 문제의 탈출 조건이 된다.

 

2. 원반이 두개인 경우(n=2)

가장 아래에 있는 큰 원반을 원반 2, 그 위에 있는 원반을 원반 1이라고 가정하자.

원반이 두 개인 경우 아래의 3단계로 문제가 해결된다.

1) 시작 기둥에 있는 원반 1이 중간 기둥으로 이동한다.

2) 시작 기둥에 있는 원반 2가 목표 기둥으로 이동한다.

3) 중간 기둥에 있는 원반 1이 목표 기둥으로 이동한다.

 

자, 이제 이를 합쳐서 1~3개인 경우를 모두 살펴보자.

 

위 과정을 쉽게 풀기 위해서는 아래와 같이 맨 아래의 원반을 제외한 나머지 n-1개의 원반을 옮기는 과정을 재귀적으로 반복하면 쉽게 해결할 수 있다.

 

파이썬 코드