[05. 재귀 알고리즘] 하노이의 탑

#include <iostream>
#include <stack>
#include <conio.h>
#include <thread>
#include <chrono>
using namespace std;

enum { SPACE = 4, MAX_HEIGHT = 10, ARROW_LENGTH = 10, WAIT_TIME = 600 };

void print_movement(int num, int x, int y) {
	static string movement = "\n";
	
	const int s = SPACE;
	const int n = ARROW_LENGTH - 2*s;
	string arrow1(n, '-');
	string arrow2(2 * n + 2 * s + 2, '-');
	string blank(n + s + 2, ' ');
	string space(s, ' ');

	if (x == 1) {
		if (y == 2)
			movement += format(" {0}{1}{2}>{1}{0}\n", num, space, arrow1);
		else // y == 3
			movement += format(" {0}{1}{2}>{1}{0}\n", num, space, arrow2);
	}
	else if (x == 2) {
		if (y == 1)
			movement += format(" {0}{1}<{2}{1}{0}\n", num, space, arrow1);
		else // y == 3
			movement += format(" {3}{1}{0}{1}{2}>{1}{0}\n", num, space, arrow1, blank);
	}
	else { // x == 3
		if (y == 1)
			movement += format(" {0}{1}<{2}{1}{0}\n", num, space, arrow2);
		else // y == 2
			movement += format(" {3}{1}{0}{1}<{2}{1}{0}\n", num, space, arrow1, blank);
	}
	cout << movement;
}

inline string make_plate(int n) {
	return string(n, '=');
}

void print_hanoi_tower(array<stack<int>, 3> st, int num, int x, int y) {
	size_t max_size = max({
		st[0].size(), st[1].size(), st[2].size(), (unsigned)MAX_HEIGHT });
	int init = true;
	while (max_size--) {
		for (int i = 0; i < 3; i++) {
			size_t size = st[i].size();
			if (i != y - 1 && max_size > size || i == y - 1 && max_size > size + 1) {
				cout << format("{:12}", ' ');
				continue;
			}

			if (i == x - 1 && !st[i].empty() && st[i].top() == num) {
				int n = st[i].top();
				cout << format("({}{:10}", n, ")");
				st[i].pop();
			}
			else if (i == y - 1 && init) {
				cout << format(" {}{:10}", num, make_plate(num));
				init = false;
			}
			else {
				if (!st[i].empty()) {
					int n = st[i].top();
					cout << format(" {}{:10}", n, make_plate(n));
					st[i].pop();
				}
			}
		}
		cout << endl;
	}
}

void wait() {
	static int input = ' ';
	if (input != 13)	// 13 == [Enter]
		input = _getch();
	else
		this_thread::sleep_for(chrono::milliseconds(WAIT_TIME));
}

array<stack<int>, 3> make_stacks(int num, int x) {
	array<stack<int>, 3> st;
	for (int i = num; i > 0; i--)
		st[x - 1].push(i);
	return st;
}

void move(int num, int x, int y) {
	num = min(num, (int)MAX_HEIGHT);		// 최대 MAX_HEIGHT로 제한.

	static array<stack<int>, 3> st = make_stacks(num, x);
	int temp = 6 - x - y;
	if (num > 1)
		move(num - 1, x, temp);

	system("cls");
	print_hanoi_tower(st, num, x, y);
	st[y - 1].push(st[x - 1].top());
	st[x - 1].pop();
	print_movement(num, x, y);
	wait();

	if (num > 1)
		move(num - 1, temp, y);
}

int main(int num) {
	move(4, 1, 3);
}

결과

Animated Output

(1)
 2==
 3===
 4====       1=


 1    -->    1

부터

                         1=
                         2==
                         3===
            (1)          4====


 1    -->    1
 2    -------------->    2
             1    -->    1
 3    -->    3
 1    <--------------    1
             2    <--    2
 1    -->    1
 4    -------------->    4
             1    -->    1
 2    <--    2
 1    <--------------    1
             3    -->    3
 1    -->    1
 2    -------------->    2
             1    -->    1

까지