[Programmers]하노이의 탑(12946번)/JS

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

---

접근 방법

사실 처음엔 n=2, n=3, n=4일때까지 손으로 쓰면서 규칙을 찾으려 했다.

n=1일때 0번, n=2일때 3번, n=3일때 7번, n=4일때 15번 

따라서 '2^n-1번 옮긴다'라는 규칙만 찾고 어떻게 구현해야될지 감이 안잡혔다❓

아래 영상보니까 어느 정도 이해됐다(사실 코드도 봐버림~)

https://youtu.be/aPYE0anPZqI

 

재귀함수 개념은 알고 있었는데, 실제로 구현하려하니까 생각도 안나고 어떻게 해야되나.. 고민이 많이 됐다.

이번 문제를 풀면서 어느정도 이해했을지두..? 

 

코드

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

    return answer;
}

hanoi 함수의 인자로 num=원판 개수, from=출발지, to=목적지, other=다른 기둥을 넣어주면 된당

n==1이면 옮길 원판이 없으니까 answer에 from,to를 넣어주고

아니면

재귀함수를 호출하는데

첫번째 재귀함수 호출은 목적지가 아닌 곳으로 가장 큰 원판만 두고 옮기는 것이고

두번째 재귀함수 호출은 목적지로 가장 큰 원판을 옮기는 것이다.

 

코드 보고도 머릿속으로 한 번에 이해가 되지 않아서 손으로 하나씩 써보면서 했다.

위의 사진은 n=4일때를 하나씩 호출해 본 것이다.

역시 머리로 이해가 안될때는 손으로 해보는게 짱인듯!!