[알고리즘/c++] - 하노이 머 하노

안녕하세요? 

오랜만에 돌아온 알고리즘 시간입니다.

오늘 배워볼 알고리즘은 바로.

두번째 앨리스 머 하노(두번째앨리스는노란쌍둥이)

하노이 머 하노

가 아니라 하노이 탑 알고리즘.

입니다.

 

---

하노이 탑 게임 

: 3개의 기둥에 적당한 개수의 원반을 쌓아놓고 다른쪽으로 원판을 올리는 게임

- 규칙 1: 작은 원반 위에 큰 원반이 올 수 없다. 

- 규칙 2: 원반을 옮기는 최소 횟수를 찾자(2개 = 3번 , 3개 = 7번)

 

하노이 탑 알고리즘은 위의 게임을 클리어하기 위한 일종의 규칙을 알고리즘으로 구현한 것을 의미합니다.

하노이 탑의 원리와 정답은 의외로 간단하면서도 쉽게 생각해내기가 어렵습니다.

https://vidkidz.tistory.com/649

하노이의 탑 (Tower of Hanoi)

위 링크는 하노이 탑 알고리즘을 플래시게임으로 구현한 사이트입니다.

게임이 이해가 가지 않는다면 간단하게 한 번씩 플레이해보는 것을 권장합니다.

 

먼저 2개의 원판이 있을 때의 최소 횟수로 첫번째 기둥에 있던 원판들을 세번째 기둥으로 모두 옮기는 예시를 그림으로 그려보았습니다.

총 3번만에 모든 원판을 옮길 수 있었습니다.

---

점화식

원판이 3개일 때에도 시도해보면 7개인것을 알 수 있고, 4개인 경우에는 15개, 5개인 경우에는 31개,...

방금 말을 잘 살펴보면 최소횟수에는 규칙이 있다는 것을 알게 됩니다!!

1개를 옮기는 데에는 1번, 2개를 옮기는 데에는 (2^2)-1 =3번. 3개를 옮길 때에는 (2^3)-1=7번..

이렇게 a(n) = 2^n-1이라는 점화식을 쉽게 구할 수 있습니다!.

정답만을 구하고 싶은거라면 이 점화식을 통해 쉽게 답을 찾을 수 있습니다.

 

알고리즘

하지만 우리가 원하는 것은 정답 뿐만이 아닙니다.. 원판이 이동하는 모든 규칙을 알고싶죠...

원판이 이동하는 데에는 일정한 규칙이 반복적으로 작용하고, 이를 통해 우리는 재귀를 활용하여 쉽게 문제를 풀 수 있습니다.

먼저, 위에서 2개를 이동하는 방법에 대해 그림으로 살펴보았는데, 이번엔 글을 통해 3개의 원판을 이동시키는 것을 보겠습니다.

1번 원판을 a->c

2번 원판을 a->b

1번 원판을 c->b

3번 원판을 a->c

1번 원판을 b->a

2번 원판을 b->c

1번 원판을 a->c

 

이렇게 봐도 무슨소리인지 잘 모르겠습니다.

그럼 끊어서 보겠습니다.

1번 원판을 a->c

2번 원판을 a->b

1번 원판을 c->b

-----------------------

3번 원판을 a->c

------------------------

1번 원판을 b->a

2번 원판을 b->c

1번 원판을 a->c

 

첫번째 작업은, 3번 원판을 이동시키기 위해 상단의 원판들이 모두 이동하는 과정

두번째작업은 하단 원판을 옮긴 작업

세번째 작업은 남은 두 원판을 모두 3번으로 이동시키는 작업

 

첫번째 작업과 세번째 작업이 모두 제가 위에서 그린 그림의 방식과 똑같습니다.

이 작업은 원판이 4개, 5개인 경우에도 동일하게 작용합니다.

 

이렇게 쉽게 규칙을 찾았습니다.

그리고 이 규칙은 

 - 1번 기둥의 n-1개의 원판을 2번으로

 - 1번 기둥의 큰 원판을 3번으로

 - 옮겨둔 2번 기둥의 원판을 3번으로 옮김

이렇게 요약할 수 있습니다.

이 과정이 n이 1이 될때까지 계속해서 반복된다면 결국에는 모든 원판이 목적지(3번)에 도착할 수 있습니다.

---

 

다음은 알고리즘을 모른 상태에서 풀었던 제 코드입니다..

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

vector<int> getlongnum(int n) {
    vector<int> tmp;
    tmp.push_back(1);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < tmp.size(); j++) {
            tmp[j] *= 2;
        }
        for (int j = 0; j < tmp.size(); j++) {
            if (tmp[j] >= 10) {
                if(j + 1 == tmp.size()) tmp.push_back(tmp[j] / 10);
                else {
                    tmp[j + 1] += tmp[j] / 10;
                }
            }
            tmp[j] %= 10;
        }
    }
    return tmp;
}

void replay(int n, int from, int to, int by) {
    if (n == 1) {
        cout << from << " " << to << "\n";
        return;
    }
    replay(n - 1, from, by, to);
    cout << from << " " << to << "\n";
    replay(n - 1, by, to, from);
}

int main() {
    unsigned long long n;

    cin >> n;
    vector<int> count = getlongnum(n);
    count[0] -= 1;
    for (int i = count.size() - 1; i >= 0; i--) {
        cout << count[i];
    }
    cout << "\n";
    if (n <= 20) replay(n, 1, 3, 2);
    return 0;
}

그리고 이 코드는 알고리즘을 활용하여 재귀를 활용하여 풀어낸 제 코드입니다.

해당 알고리즘은 재귀 문제로 시간복잡도는 O(2^n)입니다.

#include <iostream>
#include <stack>

using namespace std;

void Hanoi(int n, char from, char to, char by) {
        if (n == 1) {
            cout << n<<" "<<from << " " << to << "\n";
            return;
        }
        Hanoi(n - 1, from, by, to);
        cout << n << " " << from << " " << to << "\n";
        Hanoi(n - 1, by, to, from);
}

int main()
{
	Hanoi(3,'A', 'C', 'B');
	return 0;
}

 

확실히 규칙을 알고 구현하니 코드가 훨씬 더 깔끔하고 보기 좋게 바뀌는 모습을 볼 수 있습니다.

---

하노이 탑 알고리즘은 이동하는 게임 속 과정도 그렇지만 정답에도 점화식을 가지고 있는 등 재귀라는 알고리즘 구현방식에 가장 모범적인 문제이기에 아직까지도 많은 사랑을 받고 있는 문제입니다.

실제로 백준에 가면 하노이 관련 문제가 정말 많습니다.

 

생각보다 이해하는 데 많은 시간이 걸렸고, 사실 지금도 완전히 이해했다는 생각이 들진 않는 찝찝한 문제입니다..

저는 이 알고리즘을 정말 어린시절부터 봤습니다.. 레이튼교수 팬케이크옮기기 수수께끼에서요.. 

그때는 최소횟수를 고려하지 않고 옮기기만 하면 되었기 때문에 한 200번만에 팬케이크 3개를 겨우 옮겼습니다.

가만 생각해보면 레이튼교수 게임은 어느 개발자가 기획하고 만들어낸 게임이 아닐지.. 

알고리즘 공부를 할 때마다 문득문득 자꾸 풀어봤던 레이튼 문제와 같을 때가 많아서 자주 놀랍니다..

 

아무튼 오늘은 여기까지하고 다음에 보도록 하겠습니다..

여러분은 꼭 하노이를 마스터하시길 바랍니다,,

반응형