[JS] 하노이의 탑

재귀함수를 활용해서 풀 수 있다.

 

조금 쉽게 생각해보자.

 

10개의 하노이의 탑을 옮긴다고 해도 맨 마지막 원판과 나머지 9개의 원판으로 나눌 수 있다.

 

 

 

만약 1번에서 3번까지 옮기고 싶다면

 

9개의 원판 한덩이를 1->2로 옮기고 마지막 원판을 1->3으로 옮기고 9개의 원판 한덩이를 2->3으로 옮기면 된다.

 

 

그런데 9개의 원판을 1-> 2로 만드는건 또 8개짜리 원판과 맨 마지막 원판을 옮기는 문제로 축소시킬 수 있다.

 

이런 성질을 활용해서 아래와 같이 재귀를 활용할 수 있다.

 

 

 

function solution(n) {
    
    const ret = []
    const dfs = (n,s,e) => {
        if (n===0) return
        
        const rest = [1,2,3].filter(v => v!==s && v!== e)[0]
        dfs(n-1,s,rest)
        ret.push([s,e])
        dfs(n-1,rest,e)
    }
    
    dfs(n,1,3)
    return ret
}