하노이의 탑은 1883년 프랑스의 수학자 루카스가 발표한 게임으로, 규칙은 다음과 같다.
그림을 보면 쉽게 이해할 수 있다.
다음은 3개의 기둥과 3개의 원판이 있는 하노이의 탑이다.
1번 기둥에 3개의 원판이 꽂혀있는데 이 3개의 원판을 3번 기둥으로 옮기는 순서를 나타낸 것이다.
하노이의 탑을 자바스크립트 코드로 구현해보자
/**
* Tower of Hanoi function
* @param n {number} 원판의 수
* @param from {number} 처음 원판들이 꽂혀있는 기둥 번호 (1~3)
* @param to {number} 원판들을 옮겨야 할 기둥 번호 (from과 다른 기둥번호)
*/
function hanoi(n, from, to) {
// TODO 하노이의 탑 알고리즘을 구현하세요
/*
기둥에 있는 원판을 옮길 때 마다
"n번 기둥 맨 위의 원판을 m번 기둥으로 이동"
이라는 메세지를 console.log로 출력하세요
*/
if (n >= 1) {
const temp = 6 - from - to;
hanoi(n-1, from, temp);
console.log(`${from}번 기둥 맨 위의 원판을 ${to}번 기둥으로 이동`);
hanoi(n-1, temp, to);
}
}
//--- 실행 ---
hanoi(4, 1, 3); // 4개의 원판을 1번기둥에서 3번기둥으로 모두 옮기자
//--- 실행결과 ---
1번 기둥 맨 위의 원판을 2번 기둥으로 이동
1번 기둥 맨 위의 원판을 3번 기둥으로 이동
2번 기둥 맨 위의 원판을 3번 기둥으로 이동
1번 기둥 맨 위의 원판을 2번 기둥으로 이동
3번 기둥 맨 위의 원판을 1번 기둥으로 이동
3번 기둥 맨 위의 원판을 2번 기둥으로 이동
1번 기둥 맨 위의 원판을 2번 기둥으로 이동
1번 기둥 맨 위의 원판을 3번 기둥으로 이동
2번 기둥 맨 위의 원판을 3번 기둥으로 이동
2번 기둥 맨 위의 원판을 1번 기둥으로 이동
3번 기둥 맨 위의 원판을 1번 기둥으로 이동
2번 기둥 맨 위의 원판을 3번 기둥으로 이동
1번 기둥 맨 위의 원판을 2번 기둥으로 이동
1번 기둥 맨 위의 원판을 3번 기둥으로 이동
2번 기둥 맨 위의 원판을 3번 기둥으로 이동