하노이 탑

막대 A에 쌓여있는 n개의 원판을 막대 C로 옮기는 문제.

 

규칙 1. 한번에 하나의 원판만 이동 가능.

규칙 2. 맨 위에 있는 원판만 이동 가능.

규칙 3. 크기가 작은 원판 위에 크기가 큰 원판이 쌓일 수 없음.

 

하노이 탑 문제는 재귀적인 알고리즘을 짜면 쉽게 풀 수 있는데 다음과 같은 순서로 진행하면 이 문제를 일반적으로 풀 수 있음.

1. C를 버퍼로 사용해서 A에 쌓여있는 n-1개의 원판을 B로 이동.

2. A에 남아있는 하나의 원판을 C로 이동.

3. A를 버퍼로 사용해서 B에 쌓여있는 n-1개의 원판을 C로 이동.

 

n의 크기와 어디서(from), 어디로(to), 버퍼(tmp)를 바꿔가며 함수를 재귀적으로 호출함으로써 구현할 수 있다.

 

void hanoiTower(int n, char from, char tmp, char to)
{
    if (n == 1) printf("원판 1을 %c에서 %c로 옮긴다.\n", from, to);
    else {
        hanoiTower(n - 1, from, to, tmp);
        //1. C를 버퍼로 사용해서 A에 쌓여있는 n-1개의 원판을 B로 이동.
        printf("원판 %d를 %c에서 %c로 옮긴다.\n", n, from, to);
        //2. A에 남아있는 하나의 원판을 C로 이동.
        hanoiTower(n - 1, tmp, from, to);
        //3. A를 버퍼로 사용해서 B에 쌓여있는 n - 1개의 원판을 C로 이동.
    }
}