[자료구조/Week 07] Recursion - 하노이탑 옮기기

문제

원판이 4개일 때 하노이탑 풀이 과정 서술하기

 

코드

#include <iostream>
using namespace std;

void hanoiTower(int n, char from, char tmp, char to)
{
    if (n == 1)
    cout << "원판 1을 " << from << "에서 " << to << "로 옮긴다." << endl;
    else {
        hanoiTower(n-1, from, to, tmp); // ---> ①
        cout << "원판 " << n << "을 " << from << "에서 " << to << "로 옮긴다." << endl; // ---> ②
        hanoiTower(n-1, tmp, from, to); // ---> ③
    }
}

int main()
{
    hanoiTower(4, 'A', 'B', 'C');
}

결과

하노이탑 n = 4 일때,

원판 1을 A에서 B로 옮긴다.

원판 2을 A에서 C로 옮긴다.

원판 1을 B에서 C로 옮긴다.

원판 3을 A에서 B로 옮긴다.

원판 2을 C에서 A로 옮긴다.

원판 2을 C에서 B로 옮긴다.

원판 1을 A에서 B로 옮긴다.

원판 4을 A에서 C로 옮긴다.

원판 1을 B에서 C로 옮긴다.

원판 2을 B에서 A로 옮긴다.

원판 1을 C에서 A로 옮긴다.

원판 3을 B에서 C로 옮긴다.

원판 1을 A에서 B로 옮긴다.

원판 2을 A에서 C로 옮긴다.

원판 1을 B에서 C로 옮긴다. 끝!