프로그래머스 - 하노이 탑

 

문제

 

풀이

하노이 탑은 원판의 수 n, 시작하는 기둥 start, 중간의 거치는 기둥 mid, 도착할 기둥 end 총 4개의 요소가 필요하다

원판의 수가 1일 경우에는 start에서 바로 end로 넘기면 된다

아닐 경우에는 n-1개의 원판을 start에서 mid로 옮겨준다

n번째 원판을 start에서 end로 옮겨준다

mid에 있던 n-1개의 원판을 end로 옮겨준다

이 과정을 재귀함수를 통해 구현해준다

function solution(n) {
    let answer = [];
    
    let hanoi = (n, start, mid, end) => {
        if(n === 1) answer.push([start, end]);
        else {
        	// n-1개의 원판을 start에서 mid로 옮김
            hanoi(n-1, start, end, mid);
            // n번째 원판을 start에서 end로 옮김
            answer.push([start, end])
            // n-1개의 원판을 mid에서 end로 옮김
            hanoi(n-1, mid, start, end);
        }
    }
    
    hanoi(n, 1, 2, 3);
    
    return answer;
}