[TIL] 하노이탑

문제

답안

function solution(n) {
    var answer = [];
    
    const hanoi = (n, from ,to, via)=> {
        if(n===1){
            answer.push([from,to])
        }
        else{
            hanoi(n-1,from,via,to)
            answer.push([from,to])
            hanoi(n-1,via,to,from)
        }
    }
    hanoi(n,1,3,2)
    return answer;
}

실제 하노이탑을 움직이는 것 처럼 생각하면 편하다.
처음 hanoi함수를 실행했을 때, n=2, from=1, to=3, via=2 이다.
함수 실행하면서 첫 실행에는 n은 아직 1이 아니기 때문에 hanoi(n-1,from,via,to)를 실행하게 될 것이다. 그렇다면 via인 2를 목적지로 hanoi(1,1,2,3)이 될 것이다. 그러면 이때 n===1이기 때문에 answer에 [1,2]를 push하게 된다. 그 다음 answer.push()를 통해 처음의 [1,3]이 answer에 들어간다. 그 다음은 hanoi(1,2,3,1)이 될 것이다. 똑같은 순서대로 n===1이기 때문에 [2,3]을 push하게 된다.

순서를 정리하면

1. hanoi(n,1,3,2) => answer.push([1,2])
2. hanoi(n-1,1,2,3) => answer.push([1,3])
3. hanoi(n-1,2,3,1) => answer.push([2,3])