하노이 탑

[요약] 세 개의 막대 기둥을 이용해서 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽 기둥으로 옮기는 퍼즐 게임

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종으로 프랑스의 수학자인 에두아르 뤼카(Édouard Lucas)가 고안한 수학적 게임이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들을 활용하여 옮기는 놀이이다.

한 번에 원판 한 개씩만 옮길 수 있으며, 작은 원판이 큰 원판의 위에 있어야 한다는 규칙만 있으며, 이 문제의 풀이는 재귀 알고리즘으로 설명할 수 있다. 원반이 N개인 경우에 원반은 모두 옮기는 것은 2n-1번의 횟수가 필요하다는 것이다.

원반이 두 개일 경우(n=2)에는 3단계로 해결할 수 있다. 먼저 원반 1을 축 A에서 C로 옮기고 바닥에 있던 원반 2를 축 B로 옮긴다. 마지막으로 원반 1을 축 C에서 B로 옮기면 된다.



관련콘텐츠

1,269

2,831