들어가며

하노이의 탑 알고리즘을 처음 봤을 때 멘탈이 흔들렸다. 다른 설명을 보지 않고 내 머리로만 이해하려고 시도했다. 별로 좋은 선택이 아니었다. 스스로 시도하는 것도 좋지만 좌절할 정도로 어려운 문제는 답을 보는게 좋다. 답을 보더라도 설명할 수 있게 이해한다면 그걸로 괜찮다.

핵심 개념

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

가장 먼저 제일 밑바닥에 있는 원판이 목표 기둥에 있어야 한다. 그러기 위해선 그 위에 있는 원판들이 목표 기둥이 아닌 다른 기둥에 있어야 한다.

다른 목표 기둥들이 다른 기둥에 있기 위해서는 다른 기둥의 가장 아래 원판이 목표 기둥에 있어야 한다. 글로 풀어쓰면 어렵지만 그림으로 보면 이해가 쉽다.

가장 중요한 개념은 매번 재귀 함수가 일어날 때 마다 조건은 같게 된다. 가장 큰 원판이 밑에 있으면 된다. 그러므로 재귀가 시행되면서 이전 환경에 영향을 받지 않는다.

가장 아래 원판을 먼저 옮기고 그보다 가장 위 원판을 옮기는, 순서를 맨 아래부터 계산해 나가면 쉽게 답을 찾을 수 있다.

나의 답안

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

다른 답안

function hanoi(num, from, to, mid) {
  if (num === 0) return;
  hanoi (num - 1, from, other, to);
  console.log(`${from}번에서 ${to}로 옮긴다.`);
  hanoi (num - 1, other, to, from);
}

참고 URL

https://youtu.be/aPYE0anPZqI