문제

프로그래머스 Lv3 하노이탑

문제설명

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

제한사항

n은 15이하의 자연수 입니다.

입출력 예

n	result
2	[[1,2],[1,3],[2,3]]

내 첫생각

예전에 중학교 고등학교때 하노이탑 문제의 공식들이 있었는데 그 공식이 점화식이었고 그 점화식을 바탕으로 재귀함수를 만들면 되지 않을까... 생각했지만 찾을 수는 없었다.

풀이

내가 생각하려고 했던 공식은 1. 맨 밑에칸을 뺀 나머지를 두번째칸으로 옮긴다. 2. 맨 밑의 원판을 마지막 칸으로 옮긴다. 3. 두번째 칸으로 옮겼던 나머지를 첫번째칸으로 옮긴다. 그 이후에는 반복을 하다보면 모든 원판이 마지막 칸으로 옮겨질 것이다

정리해보자면 아래와 같다.
1. A 기둥에 있는 n-1 번째 원판을 B 기둥으로 이동한다.
2. A 기둥에 있는 n 번째 원판을 C 기둥으로 이동한다.
3. B 기둥에 있는 n-1 번째 원판을 C 기둥으로 이동한다.

재귀함수로 표현해 보면 아래와 같다.

function solution(n) {

    var answer = [];

  function move (start, mid, end, weight) {
    if(weight === 1) {                                      
      answer.push([start, end]);
    } else {                                                
      move(start, end, mid, weight-1);           
      answer.push([start, end]);                 
      move(mid, start, end, weight-1);           
    }
  }

  move(1,2,3,n);

    return answer;
}