[재귀] 하노이의 탑

규칙:

1. 각 원반은 자신보다 큰 원반 위에만 올 수 있다.
2. 한 번에 옮길 수 있는 것은 한개의 원반밖에 없다.

어떻게 해결해야 할까?

한 번 직접 원반이 있다 생각하고, 그림으로 표현하면 이렇다.

이미지 출처: https://shoark7.github.io/programming/algorithm/tower-of-hanoi



1. 작은 원반 n-1개를(맨 아래 원반을 제외한 원반들)을 A에서 B로 이동
2. 큰 원반(맨 아래 원반) 1개를 A에서 C로 이동
3. 작은 원반(1단계에서의 원반) n-1개를 B에서 C로 이동

즉, 원래 있던 기둥에서 목표로 하는 기둥으로 옮기기 위해, 나머지 다른 기둥으로 옮긴다.

이것을 재귀적으로 수행하면, 원반을 분리시킬 수 있다.

그리고 난 후, 분리했던 원반들을 목표로 하는 기둥으로 다시 합치는 작업을 재귀적으로 수행한다.

이것을 코드로 표현하면 아래와 같다.

#include <iostream>
using namespace std;

// from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from , char by, char to)
{
    if(num == 1)
    {
        printf("원반 1을 %c에서 %c로 이동\n", from, to);
    }
    else
    {
        HanoiTowerMove(num-1, from, to, by);
        printf("원반 %d를 %c에서 %c로 이동\n", num, from, to);
        HanoiTowerMove(num-1, by, from, to);
    }
}

옮기는 원반이 1개라면, 옮기고 탈출

아니라면, 맨 밑 원반을 남기고, to로 옮기려 했던 곳에 윗 원반들을 옮김.(재귀)

by에 놨던 원반들을 to쪽으로 옮김(분리해놨던 원반들을 합침)