[프로그래머스] 하노이의 탑

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

프로그래머스

 

학생때 풀었던 문제죠? 

근데 기억안나서 게시판에서 해설 보고 이해했다...재귀 공부 하자 .. 

 

function solution(n) {
 
    var answer = [];
    
    function hanoi(n,start,end,mid){
        if(n==1){
            answer.push([start,end]);
            return;
        }
        else{
            hanoi(n-1,start,mid,end);
            answer.push([start,end]);
            hanoi(n-1,mid,end,start);
        }
    }
    hanoi(n,1,3,2);
    return answer;
}

 

예제에서나오는 원반이 2개 있을때

작은 원반을 중간으로, 큰원반을 끝으로 보낸 다음, 다시 작은 원반을 끝으로 보내는 과정을

예로 들어 설명하면, 

 

 

1. hanoi(n-1,start,mid,end) = hanoi(1,1,2,3)

> n==1 이므로 [1,2] push 후 return

 

2.answer.push([start,end])  

>처음의 hanoi(n,1,3,2)에서 start end인 [1,3] push

 

3.hanoi(n-1,mid,end,start) = hanoi(1,2,3,1)

>n==1이므로 [2,3] push 후 return