하노이 탑(Hanoi Tower)

하노이 탑문제는 N개의 크기가 서로 다른 원판을 다른 기둥으로 옮기는 문제이다.

이 때 다음 두 가지 조건을 만족시키면서 원판을 다른 기둥으로 옮겨야 한다.

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안된다.

---

전체 n개의 원판을 옮기는 것은 다음과 같이 재귀적으로 생각해 볼 수 있다.

1. 크기 1 ~ (n-1)인 원판들을 A기둥에서 B기둥으로 옮긴다.
2. 크기 n인 원판을 A기둥에서 C기둥으로 옮긴다.
3. 1 ~ (n-1) 원판들을 B기둥에서 C기둥으로 옮긴다.

---

소스코드

void hanoi(int n, char from, char tmp, char to)
{
    if(n > 0)
    {
        hanoi(n-1, from, to, tmp);
        cout<< n << " : " << from << " -> " << to << endl;
        hanoi(n-1, tmp, from, to);
    }
}

원판의 크기를 n이라 할 때, n은 자연수이므로 (n > 0)가 아닌 경우를 탈출 조건으로 한다.

---

전체 소스코드

#include <iostream>

using namespace std;

void hanoi(int n, char from, char tmp, char to)
{
    if(n > 0)
    {
        hanoi(n-1, from, to, tmp);
        cout << n << " : " << from << " -> " << to << endl;
        hanoi(n-1, tmp, from, to);
    }
}

int main()
{
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}