(Programmers) [Lv.2] 하노이의 탑

• 문제 설명
  • 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
    • 한 번에 하나의 원판만 옮길 수 있습니다.
    • 큰 원판이 작은 원판 위에 있어서는 안 됩니다.
    • 하노이 탑의 세 개의 기둥을 왼쪽부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
    • 1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return 하는 solution를 완성해 주세요.
      
      
• 문제의 제한사항
  • n은 15 이하의 자연수입니다.
    
    
• 입출력 예시

하노이의탑에 대한 예시

 

• 해결방안
  • 원판개수에 상관없이 원판 전체를 크게 2개로 나눠어서 생각했다
    • 제일 큰판과 그 나머지 원판들
      
      1. 제일 큰 판을 제외한 나머지 원판들을 최종 목적지가 아닌 기둥에 옮긴다.
      2. 제일 큰 판을 최종 목적지로 옮긴다
      3. 나머지 원판들을 최종 목적지로 옮긴 제일 큰 판 위로 옮긴다

 

• 전체 코드

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