[프로그래머스] Lv.02 연습문제 하노이의 탑 (JavaScript)

문제 설명

퍼즐 게임으로 유명한 하노이의 탑은 원판을 마지막 기둥으로 모두 옮기면 끝나는 게임이다.

규칙 크게 두가지가 있다. 

첫 번째는 한 번에 하나의 원판만 옮길 수 있다이고, 두 번째는 큰 원판이 작은 원판 위에 있어서는 안된다는

규칙이다.

위에 규칙을 준수하면서 첫 번째 기둥에 있는 모든 원판을 세 번째 기둥으로 최소한의 이동으로 옮겨주면 된다.

 

※ 제한사항 :  원판의 개수는 15이하의 자연수이다.

풀이

문제에서는 원판의 개수를 가르키는 변수 n(int)이 주어진다. n의 개수가 정해져 있지 않기 때문에 단순 반복으로 접근하기에는 무리가 있다고 생각을 하였다. 그래서 재귀를 이용해 접근하였다. 처음 hanoi(n, 1, 3, 2, answer) 이러한 함수 형태로 요청을 하면 hanoi(n-1, start, sub, end, answer) / hanoi(n-1, sub, end, start, answer) 이와 같은 형태로 재귀 호출을 해 n이 1이 될때까지 반복을 해서 모든 원판이 마지막 기둥으로 향하도록 설계하였다.

아래 풀이에 사용한 코드이다.

function solution(n) {
    var answer = []; // 지나간 경로를 저장하는 변수
    let result = hanoi(n, 1, 3, 2, answer) // hanoi 함수 호출
    return result;
}

// 재귀 형태의 hanoi 함수
// 순차적으로 재귀형태로 호출
function hanoi(n, start, end, sub, answer){
    if(n==1){
        answer.push([start, end])
    }else{
        hanoi(n-1, start, sub, end, answer)
        answer.push([start, end])
        hanoi(n-1, sub, end, start, answer)
    }
    
    return answer
}