하노이 타워 문제

하노이 타워 문제

• 너무 유명한 문제이기 때문에 문제는 생략.

• 재귀를 이용할 수 있는지를 알아보는 문제.

#include <cstdio>
​
void Move(int id, char from, char to) {
    printf("[원판%d] %c -> %c\n",id, from, to);
}
​
//from에 꽂혀있는 num개의 원판을 by를 거쳐서 to로 이동.
void SolveHanoi(int num, char from, char by, char to)
{
    if (num == 1) {
        Move(1, from, to);
        return;
    }
​
    SolveHanoi(num - 1, from, to, by);
    Move(num, from, to);
    SolveHanoi(num - 1, by, from, to);
}
​
int main() {
    SolveHanoi(5, 'A', 'B', 'C');
}

• 가장 큰 원판을 제외하고, 나머지를 from에서 by로 옮긴다.

• 가장 큰 원판을 from 에서 to로 옮긴다.

• by로 옮겼던 나머지를 to로 옮긴다.

• 시간복잡도는 ​