지난 글 : [알고리즘/알고리즘 도감] - 페이지랭크
하노이의 탑은 원반을 이동해 탑을 쌓는 게임이다. 재귀적인 알고리즘을 쉽게 이해할 수 있는 예로 대표적이다.
참고 : [알고리즘/Do it 알고리즘] - 하노이의 탑
1
1 | |
2 | |
3 | |
===== ===== =====
A B C위 그림에는 A, B, C 세 개의 기둥이 있으며, A 기둥에 3개의 원반이 꽂혀 있다. 이것이 초기 상태다. 3개의 원반을 순서를 유지한 채 C 기둥으로 이동하는 것이 게임의 목적이다. 원반의 이동에는 아래 두 가지 조건이 있다.
1. 한 번에 한개의 원반만 이동할 수 있다.
2. 작은 원반 위에 그것보다 큰 원반을 둘 수 없다.위 조건 하에 모든 원반을 마지막 기둥으로 이동하는 것이 게임의 목표이며 이 과정에서 B나 C를 사용해 원반들을 임시로 움직일 수 있다.
2
원반에서 가장 큰 원반을 제외한 나머지 원반들을 '그룹'으로 묶어 생각해보면 풀이는 간단하다.
| | |
| 1 |
3 2 |
===== ===== =====
A B C원반 1과 2가 '그룹'으로 묶여 B기둥으로 이동하고,
| | |
| 1 |
| 2 3
===== ===== =====
A B C원반 3을 목표 기둥인 C로 이동한 후,
| | 1
| | 2
| | 3
===== ===== =====
A B C'그룹'을 기둥 C로 이동하면 된다.
참고 서적 :
