하노이 타워는 대표적인 재귀 알고리즘입니다.
하노이 타워 알고리즘은 n 개의 돌을 이동시키는 문제입니다. 세 개의 기둥이 있고 하나의 기둥에 n 개의 돌이 크기 순으로 있습니다. 한 번에 하나의 돌을 이동할 수 있고 작은 돌 위에 큰 돌이 올 수 없습니다. 이와 같은 규칙을 이용하여 n 개의 돌이 있는 기둥에서 다른 기둥으로 모든 돌을 옮기는 문제입니다.
이 문제를 재귀적으로 해결하면 다음처럼 해결할 수 있습니다.
가정: n-1개의 돌을 옮길 수 있다.
가정에 의해 먼저 A에 있는 n-1개의 돌을 C를 이용하여 B로 옮깁니다.
규칙에 의해 1개의 돌을 A에서 C로 옮깁니다.
가정에 의해 B에 있는 n-1개의 돌을 A를 이용하여 C로 옮깁니다.
따라서 n개의 돌을 옮길 수 있습니다.
의사코드(pseudo code)로 나타내면 다음처럼 표현할 수 있습니다. 탈출 조건을 표현하고 있음을 확인하세요.
Hanoi(src, use, dest, n)
조건 n<=0
종료
Hanoi(src,dest,use,n-1)
Move(src,dest)
Hanoi(use,src,dest,n-1)
재귀 호출하면 이전보다 n을 1 감소하므로 탈출 조건에 근접함을 알 수 있습니다.
하노이 타워 알고리즘을 구현합시다.
#include <iostream>
#include <string>
using namespace std;
//알고리즘은 입력 인자로 세 개의 기둥과 돌의 개수를 받아야 합니다.
void Hanoi(string src, string use, string dest, int n)
{
//돌이 없을 때는 아무것도 수해하지 않고 알고리즘을 끝냅니다. 즉 탈출 조건입니다.
if(n<=0) //돌이 없을 때
{
return;
}
//n-1개의 돌을 src에서 dest를 이용하여 use로 옮깁니다.
Hanoi(src,dest,use,n-1); //n-1 개의 돌을 src에서 dest를 이용하여 use로 이동
//src에 있는 돌을 dest로 옮깁니다.
cout<<"move "<<src<<" -> "<<dest<<endl; //scr에서 dest로 이동
//use에 있는 n-1개의 돌을 src를 이용하여 dest로 옮깁니다.
Hanoi(use,src,dest,n-1); //n-1개의 돌을 use에서 src를 이용하여 dest로 이둉
}
int main()
{
Hanoi("a","b","c",3);
return 0;
}
▷ 실행 결과
move a -> c move a -> b move c -> b move a -> c move b -> a move b -> c move a -> c