각기 다른 크기의 원판들과 판 위에 세워진 세개의 막대로 구성된다. 원판의 순서를 유지한 채 마지막 막대로 옮기는 문제이다. 작은 원판 위에 큰 원판이 올 수 없다.
이러한 과정을 거쳐 간다.
function solution(n) {
const answer = [];
const hanoi = (num, start, mid, end) => {
if(num === 1){
answer.push([start, end]);
return;
}
// 목적지를 가운데로 설정하고 재귀를 쭉 들어감
hanoi(num - 1, start, end, mid);
answer.push([start,end]);
// 앞 재귀가 끝나고 시작을 가운데, 목적지를 마지막으로하고 재귀가 들어감
hanoi(num - 1, mid, start, end);
}
hanoi(n, 1,2,3);
return answer;
}
n 개의 원판을 옮기는 함수이다.
n개의 원판을 1번 기둥에서 3번 기둥으로 옮기기 위해서는
n-1개의 원판을 1번에서 2번 기둥으로 옮기고, 남아있는 원판을 1번에서 3번으로 옮긴다. 그리고 2번으로 옮겼던 n-1개의 원반을 3번으로 옮긴다.
원판이 하나만 남는다면, 시작점에서 끝점으로 옮기고 재귀를 끝낸다.
하노이 탑 원판이 n개 일 때, 총 이동횟수는
2^n - 1 이된다.