언제나 처음처럼

[문제 링크]

하노이탑은 1번 막대(from)에서 시작하는 경우 2번 막대(by)를 거쳐 3번 막대(to)에 쌓는다.

즉 1번 막대(from)에서 마지막 원판을 제외한 n-1개 원판을 3번 막대(to)를 거쳐 2번 막대(by)에 쌓은 다음, 남은 원판을 목적지인 3번 막대(to)에 쌓고, 원판이 쌓인 막대가 바뀌었으니 똑같이 2번 막대에서 1번 막대를 거쳐 3번 막대에 쌓는 작업을 반복하는 것이다.

이는 움직이기 전 하노이탑에서 시작 지점과 원판 갯수(n)만 바뀐 같은 문제가 반복되는 형태라는 것을 알 수 있고, 이는 분할 정복 알고리즘을 통해 해결할 수 있다.

하노이탑 이동 횟수는 원판수(n)에 따라 정해진 공식이 있지만, 본 코드에서는 cnt라는 변수로 횟수를 카운팅하고, 이동 경로를 queue에 담아 마지막에 출력해주는 형태로 구현하였다.

#include <iostream>
#include <queue>
using namespace std;

queue<pair<int, int>> moving;
int cnt;
void hanoi(int n, int from, int by, int to) // from에서 by를 거쳐 to로
{
	if (n == 1)
	{
		moving.push(make_pair(from, to));
		cnt++;
	}
	else
	{
		hanoi(n - 1, from, to, by);
		moving.push(make_pair(from, to));
		cnt++;
		hanoi(n - 1, by, from, to);
	}
}

int main(void)
{
	int n;
	cin >> n;
	hanoi(n, 1, 2, 3);
	cout << cnt << endl;
	while (!moving.empty())
	{
		cout << moving.front().first << ' ' << moving.front().second << '\n';
		moving.pop();
	}
	return 0;
}

알고리즘 200일 프로젝트 - 36day