문제55. 공포의 하노이의 탑

하노이의 탑은 A,B,C 3개의 기둥과 기둥에 꽂을 수 있는 N개의 원판으로 이루어져 있음

 

• 다음의 규칙을 만족해야함

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

• A 기둥의 원반 N개를 모두 C원반으로 옮기고 싶다.
• 모든원반을 옮기기 위해 실행되어야할 최소 원반 이동 횟수를 계산하여라.

 

 

미리 생각해 봐야할 것

원반 갯수(n)에 따른 이동 횟수

• n = 1, 1번
  n = 2, 3번
  n = 3, 7번
  n = 5, 15번

 

다음과 같은 점화식을 가진다

• 2^n - 1 = 이동횟수
  
  

그렇다면 이동경로는 어떻게 추적할수 있을까?

• 위와 같은 점화식에 재귀함수를 이용하여 추적해보자

 

 정답

const route = [];

function hanoi(원반의수, 시작기둥A, 목표기둥C, 보조기둥B){
  // 원판이 한개 일때는 바로 옮기면 됩니다.
  if (원반의수 === 1){
    route.push([시작기둥A, 목표기둥C]);
    return 1;
  }

  // 원반이 n-1개를 보조기둥으로 옮기고
  hanoi(원반의수-1, 시작기둥A, 보조기둥B, 목표기둥C)
  // 가장 큰 원반은 목표기둥C으로
  route.push([시작기둥A, 목표기둥C])
  // 보조기둥과 시작기둥A을 바꿉니다.
  hanoi(원반의수-1, 보조기둥B, 목표기둥C, 시작기둥A) 
}

hanoi(3, 'A', 'C' ,'B');
console.log(route); // 이동경로
console.log(route.length);

다음과 같이 출력된다

 

> 역추적

function hanoi(원반의수, 시작기둥A, 목표기둥C, 보조기둥B){ } 를 하나하나 살펴보자 !

1. 원반이 하나일 때는 시작A -> 목표C 로 바로 이동을 하면된다.

  if (원반의수 === 1){
    route.push([시작기둥A, 목표기둥C]);
    return 1;
  }

 

2. 원반갯수를 3으로 가정했을때

  // 원반이 n-1개를 보조기둥B로 옮기고
  hanoi(원반의수-1, 시작기둥A, 보조기둥B, 목표기둥C)
  // 가장 큰 원반은 목표기둥C으로
  route.push([시작기둥A, 목표기둥C])
  // 보조기둥B과 시작기둥A을 바꿉니다.
  hanoi(원반의수-1, 보조기둥B, 목표기둥C, 시작기둥A)

3. 재귀함수의 호출순서를 따져보며 결과 도출을 생각해보자

function 하노이(3, 'A', 'C' ,'B')
 function 하노이(2, 'A', 'B' ,'C')
  function 하노이(1, 'A', 'C' ,'B')
   원판의이동경로.push('A', 'C') // 1번째 
  원판의이동경로.push('A', 'B')// 2번째
  function 하노이(1, 'C', 'B', 'A')
   원판의이동경로.push('C', 'B')// 3번째
   ----------------------------------- 1바퀴

   원판의이동경로.push('A', 'C')// 4번째

function 하노이(2, 'B', 'C' ,'A')
 function 하노이(1, 'B', 'A' ,'C')
    원판의이동경로.push('B', 'A') // 5번째
  원판의이동경로.push('B', 'C')// 6번째
  function 하노이(1, 'A', 'C', 'B')
    원판의이동경로.push('A', 'C')// 7번째
   ----------------------------------- 2바퀴