문제

하노이의 탑은 프랑스 수학자 에두아르드가 처음으로 발표한 게임입니다. 하노이의 탑은 A, B, C 3개의 기둥과 기둥에 꽂을 수 있는 N 개의 원판으로 이루어져 있습니다. 이 게임에서는 다음의 규칙을 만족해야 합니다.

1. 처음에 모든 원판은 A 기둥에 꽂혀 있다.
2. 모든 원판의 지름은 다르다.
3. 이 원반은 세 개의 기둥 중 하나에 반드시 꽂혀야 한다.
4. 작은 원반 위에 큰 원반을 놓을 수 없다.
5. 한 번에 하나의 원판(가장 위에 있는 원판)만을 옮길 수 있다.

이 규칙을 만족하며 A 기둥에 있는 원반 N 개를 모두 C 원반으로 옮기고 싶습니다.
모든 원반을 옮기기 위해 실행되어야 할 최소 원반 이동 횟수를 계산하는 프로그램을 완성해 주세요.

해결방안

먼저 원반의 개수에 따라 어떻게 옮겨야 하는지 말로 풀어보겠다. 최상단 원반을 1번 원반이라고 하겠다.

원반이 1개일 때,

• 1) 시작 기둥에서 목표 기둥으로 옮기기만 하면 된다.

원반이 2개일 때,

• 1) 2번 원반이 목표 기둥에 가려면 1번 원반이 중간 기둥에 있어야 하므로, 1번 원반을 중간 기둥으로 옮긴다.
• 2) 2번 원반을 목표 기둥으로 옮긴다.
• 3) 1번 원반도 목표 기둥으로 옮긴다.

원반이 3개일 때,

• 1) 3번 원반이 목표 기둥에 가려면 1, 2번 원반이 중간 기둥에 있어야 하므로, 1번 원반을 목표 기둥으로 옮긴다.
• 2) 2번 원반을 중간 기둥으로 옮긴다.
• 3) 1번 원반을 중간 기둥을 옮긴다.
• 4) 이제 1, 2번 원반이 중간 기둥에 있으므로, 3번 원반을 목표 기둥으로 옮긴다.
• 5) 위에서 원반이 2개일 때의 방법 그대로, 시작 기둥을 경유지 삼아 1, 2번 원반을 목표 기둥으로 옮기기 위해 1번 원반을 시작 기둥으로 옮긴다.
• 6) 2번 원반을 목표 기둥으로 옮긴다
• 7) 1번 원반을 목표 기둥으로 옮긴다.

원반이 3개인 경우까지 해본 결과, 결국 최하단 원반이 하나 남을 때까지 나머지 원반들을 남는 기둥에 옮겨놓고, 최하단 원반을 목표 기둥으로 옮기는 것의 재귀 반복이다. 이때, 시작 기둥, 중간 기둥, 목표 기둥은 계속 바뀐다.

const routes = [];

function hanoi(num, from, temp, to) {
  // 원판이 한 개일 때는 from에서 to 기둥으로 바로 옮기면 된다.
  if (num === 1) {
    routes.push([from, to]);
    return;
  }

  // 한 개가 아닐 때는,
  // 최하단 원반을 제외한 n-1개의 원반들을 to 기둥을 경유해서 temp 기둥에 옮긴다.
  hanoi(num - 1, from, to, temp);
  // 위의 재귀가 끝난 후엔 최하단 원반 하나가 from 기둥에 남아있고,
  // to 기둥이 비어있으므로 최하단 원반을 to 기둥으로 옮긴다.
  routes.push([from, to]);
  console.log(`${from}에서 ${to}로 이동`);
  // temp 기둥에 있던 원반들을 from을 경유해서 to 기둥에 옮긴다.
  hanoi(num - 1, temp, from, to);
}

hanoi(3, "A", "B", "C");
console.log(routes);
console.log(routes.length);