제코베 JS 100제 / 55 / 하노이의 탑

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

 

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

 

이 규칙을 만족하며 A 기둥에 있는 원반 N개를 모두 C 원반으로 옮기고 싶습니다.

모든 원반을 옮기기 위해 실행되어야 할 최소 원반 이동 횟수를 계산하는 프로그램을 완성해 주세요.

 

const route = [];

function hanoi(num, start, temp, end) {
  // 원판이 한 개일 때에는 바로 옮기면 된다.
  if (num === 0) return;

  // n-1개를 경유기둥으로 옮기고
  hanoi(num - 1, start, end, temp);
  // 가장 큰 원판은 목표 기둥으로
  route.push([start, end]);
  // 경유기둥과 시작기둥을 바꾼다.
  hanoi(num - 1, temp, start, end);
}

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

/*
[
  [ 'A', 'C' ],
  [ 'A', 'B' ],
  [ 'C', 'B' ],
  [ 'A', 'C' ],
  [ 'B', 'A' ],
  [ 'B', 'C' ],
  [ 'A', 'C' ]
]
7
*/