baekjoon. 하노이 탑 이동 순서

풀이

대표적인 재귀 문제이다

n-1개 만큼 즉 바닥에 있는 제일 큰 원판을 뺀 나머지를 2번에 옮기고 제일 큰 원판을 3번에 놓은 뒤 더 이상 이동할 필요가 없기 때문에 원판을 제외시키고

2번에 있는 원판 중 제일 큰 원판을 뺀 n-1만큼 1번으로 옮긴 뒤 제일 큰 원판을 3번으로 이동 시키는 것을 재귀적으로 구현하면 된다

구현

//const input = Number(require("fs").readFileSync("/dev/stdin").toString());
const input = 4;
const stack = [];

function hanoi(n,from,to){
    const by = 6 - from - to;
    if(n===1) {
        stack.push([`${from} ${to}`]);
        return ;
    }
    hanoi(n-1,from,by);
    stack.push([`${from} ${to}`]);
    hanoi(n-1,by,to);
}

hanoi(input, 1 ,3);
console.log(stack.length);
console.log(stack.join('\n'));

이동 경로를 표시하기위해 stack에 원판을 이동시킬 때 마다 push해 주었다