하노이의 탑(Tower of Hanoi)

하노이의 탑(Tower of Hanoi)

출처 : 구체수학, 수학독본

• 프랑스 수학자 에두아르 뤼카가 1883년에 고안한 퍼즐
  • 원반 여덟 개로 된 탑으로 시작
  • 원반들은 세 개의 기둥 중 하나에 큰 것부터 크기순으로 쌓여 있다(꼭대기에 제일 작은 원반)
  • Goal: 원반을 하나씩 이동해서 탑 전체를 다른 기둥으로 옮기는 것
    • 단, 작은 원반 위에 큰 원반을 놓아서는 안된다는 규칙이 있다.

1. 일반화
   • 원반이 n개의 경우
     • small case들을 살펴보는 것부터 시작
2. 적절한 표기법
   • 규칙에 따라 다른 한 기둥으로 옮기는데 필요한 최소한의 이동 횟수를 $T_n$으로 표기
     • $T_1$이 1이고 $T_2$는 3이다.
3. Think small
   • $T_0$은 0
4. Think big
   • 원반 세 개의 경우
     • 위에서 2번째 원반까지 가운데 기둥으로 옮기고, 마지막 제일 큰 원반을 목표 기둥으로 옮기고, 가운데 있는 두 원반을 세번째 기둥으로 옮기는 것이다.
       • 여기서 n개의 원반을 옮기는 문제의 힌트가 있다.

         1. 가장 작은 원반부터 n-1개를 다른 기둥으로 옮기고(필요한 이동 횟수 $T_{n-1}$)

         2. 가장 큰 원반을 또 다른 기둥으로 옮기고(필요 이동 횟수 1)

         3. 남은 원반 n-1개를 옮기는 것(필요한 이동 횟수 $T_{n-1}$)

            $\therefore\;T_0=0,\;T_n=2T_{n-1}+1,\;n\gt0$

            위 같은 등식을 점화식(recurrence formula)또는 점화관계식(recurrence relation)이라 부른다.

   • 수학적 귀납법
     • 원반의 개수에 따른 이동 횟수를 세어보면
       • $T_3=2\cdot3+1=7$
       • $T_4=2\cdot7+1=15$
       • $T_5=2\cdot15+1=31$
       • $T_6=2\cdot31+1=63$
       • $T_n=2\cdot T_{n-1}+1=2^n-1, n\ge0$
     • 수학적 귀납법(mathematical induction)은 정수 n에 관한 어떤 명제가 모든 $n \ge n_0$에 대해 참임을 증명하는 방법.
       • $n=1$일 때 $P(n)$이 성립하고 $n=k$일때 성립한다고 가정 → $n=k+1$일 때에도 $P(n)$성립, 즉 $P(k)→P(k+1)$
         • $T_n=2^n - 1$에서 1을 넣으면 성립
         • $T_{k+1}=2\cdot T_k + 1=2^{k+1} - 1$에서 $T_k$는 $2^n - 1$이며 $2\cdot (2^n-1) + 1=2^{k+1} - 1$ 따라서 $k+1$일 때도 성립

풀이

출처 : Accelerated Computer Science Fundamentals Specialization(Coursera)

원반 4개인 경우

Solution 1.

• Check the movement and see the pattern. S is a stack, M is a movement.

  S	M	S
  0	→	1
  0	→	2
  1	→	2
  0	→	1
  0	←	2
  1	←	2
  0	→	1
  0	→	2
  1	→	2
  0	←	1
  0	←	2
  1	→	2
  0	→	1
  0	→	2
  1	→	2

  • 0, 0, 1과 1, 2, 2의 반복된 패턴을 볼 수 있다.

  • 원반의 이동, 즉 화살표만 다르다.

    while (target 기둥의 원반 갯수가 4개인가?) // 목표 기둥에 원반 4개가 없으면 1, 아니면 0
    {
    	pattern(0, 1)
    	pattern(0, 2)
    	pattern(1, 2)
    }
    
    pattern(기둥의 인데스 1, 기둥의 인덱스 2) // 두 인자를 받는다.
    {
    	if 1의 기둥에 원반이 없으면서 2의 기둥에 원반이 있으면
    		2에 있는 원반을 1로 옮긴다
    	else if 1의 기둥에 원반이 있으면서 2의 기둥에 원반이 없으면
    		1에 있는 원반을 2로 옮긴다.
    	else if 1의 기둥에 원반이 있으면서 2의 기둥에도 원반이 있으면
    	{
    		1의 기둥에서 제일 위에 있는 원반의 크기와 2의 기둥에서 제일 위에 있는 원반의 크기 비교
    		1의 기둥의 원반의 크기가 작으면 2의 기둥으로 이동
    		아니면 2의 기둥의 원반을 1의 기둥으로 이동
    	}
    }

Solution 2

원반 4개인 경우

1. 가장 큰 원반을 제외한 원반들을 하나의 기둥으로 옮긴다

2. 마지막 제일 큰 원반을 목표 지점의 기둥으로 옮긴다.

3. 나머지 원반들을 제일 큰 원반이 있는 기둥으로 옮긴다.

   여기서 마지막 원반이 없다고 가정하며, 목표 기둥은 위에서 제일 큰 원반이 있는 기둥이 아닌 다른 기둥

   1. 가장 큰 원반을 제외한 원반들, 즉 2개의 원반을 하나의 기둥으로 옮긴다.

   2. 가장 큰 원반을 목표 기둥으로 옮긴다.

   3. 2개의 원반을 가장 큰 원반 위로 옮긴다.

      여기서 또 마지막 원반이 없다고 가정하며, 목표 기둥은 위의 기둥과 다른 기둥

      1. 둘 중 작은 원반 하나를 다른 기둥으로 옮긴다.
      2. 큰 원반을 목표 지점으로 옮긴다.
      3. 작은 원반을 큰 원반 위로 올린다.
         • 원반이 하나 남았을때, 위의 목표 지점과는 다른 기둥으로 옮긴다.

   위에서 하나의 패턴을 볼 수 있다.

   • 원반이 하나씩 없앨때마다 목표 기둥이 바뀐다.

조금 더 자세히

4개의 원반인 경우

• 높이는 4, 높이의 index 범위(0 ~ 3)
• 기둥 3개, index 범위(0 ~ 2), 0 - Source, 1 - Spare, 2 - Target.
  • 여기서 Target과 Spare는 높이에 따라 바뀐다.

Goal : 4개의 원반을 목표 기둥으로 이동

[num] - 기둥, {num} - 원반, → - movement

move(Source[0]{0..3} → Target[2])

1. move(Source[0]{1..3} → Spare[1])
   1. move(Source[0]{2..3} → Spare[1])
      1. move(Source[0]{3..3} → Spare[1])
         • move(Source[0]{3} → Spare[1])
      2. move(Source[0]{2} → Target[2])
         • move(Source[0]{2} → Target[2])
      3. move(Spare[1]{3..3} → Target[2])
         • move(Spare[1]{3} → Target[2])
   2. move(Source[0]{1} → Target[1])
      • move(Source[0]{1} → Target[1])
   3. move(Spare[2]{2..3} → Target[1])
      1. move(Source[2]{3..3} → Spare[0])
         • move(Source[2]{3} → Spare[0])
      2. move(Source[2]{2} → Target[1])
         • move(Source[2]{3} → Target[1])
      3. move(Spare[0]{3..3} → Target[1])
         • move(Spare[0]{3} → Target[1])
2. move(Source[0]{0} → Target[2])
   • move(Source[0]{0} → Target[2])
3. move(Spare[1]{1..3} → Target[2])
   1. move(Spare[1]{2..3} → Source[0])
      1. move(Spare[1]{3..3} → Target[2])
         • move(Spare[1]{3} → Target[2])
      2. move(Spare[1]{2} → Source[0])
         • move(Spare[1]{2} → Source[0])
      3. move(Target[2]{3..3} → Source[0])
         • move(Target[2]{3} → Source[0])
   2. move(Spare[1]{1} → Target[2])
      • move(Spare[1]{1} → Target[2])
   3. move(Source[0]{2..3} → Target[2])
      1. move(Source[0]{3..3} → Spare[1])
         • move(Source[0]{3} → Spare[1])
      2. move(Source[0]{2} → Target[2])
         • move(Source[0]{2} → Target[2])
      3. move(Spare[1]{3..3} → Target[2])
         • move(Spare[1]{3} → Target[2])

많이 헷갈릴 수 있다.

void move(uint16_t start, uint16_t end, Stack& source, Stack& spare, Stack& target)
{
	if (start == end) {
		target.push_back(source.removeTop())
	} else {
		move(start+1, end  , source, target, spare);
		move(start  , start, source, spare , target);
		move(start+1, end. , spare , source, target);
	}
}

// 호출시 인자의 값을 확인
move(가장 낮은 높이, 가장 높은 높이, 시작 기둥, 여분 기둥, 목표 기둥);

끝.