하노이의 탑

하노이 탑이란 1883년 프랑스 수학자 루카스(Lucas)에 의해 고안된 문제인데, 가운데 기둥을 이용해서 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽 기둥으로 옮기는 문제였다. 이때 원판은 한번에 한 개씩만 옮길 수 있으며, 작은 원판 위에 큰 원판이 놓일 수 없다는 조건이 따른다.

최소 이동 횟수를 구하거나 원반의 이동 순서를 출력하는 문제가 나온다.

 

[참고] https://shoark7.github.io/programming/algorithm/tower-of-hanoi

[참고] https://splendidlolli.tistory.com/344

 

공식의 개념을 이해하라면 우선, 

n개의 원반을 '맨 아래 원반'과 '나머지 원반묶음'이라는 두 분류로 봐야한다.

그리고 나서 다시 '맨 아래 원반'과 '나머지 원반묶음'으로 나누는 방식을 재귀적으로 바라볼 수 있다.

*기둥은 출발점, 경유점, 도착점 3개가 있다.

1. 첫 번째 재귀에서는 출발점 맨 아래 n번째 원반을 목적지로 옮기기 위해 위의 원반 묶음 n-1개를 경유지로 옮긴다.

2. 그 다음 n 번째 원반을 목적지로 옮긴다.(출력하기)

3. 경유지에 있는 원반 묶음 n-1개를 도착점으로 옮긴다.

#include <string>
#include <vector>

using namespace std;

void hanoitop(string start, string mid, string end, int n)
{
    if(n == 1)
    {
        cout << start << " " << end << endl;
        return;
    } 
        
    hanoitop(start, end, mid, n - 1);
    cout << start << " " << end << endl;
    hanoitop(mid, start, end, n - 1);
}