[Algorithm] 하노이 탑(Tower of Hanoi)

하노이 탑(Tower of Hanoi)

개념

Edouard Lucas (1842-1891)

• 프랑스의 수학자 에두아르 뤼카(François Édouard Anatole Lucas)가 1883년 소개한 유명한 문제
• 재귀(Recursion)를 연습하는데 도움이 되는 알고리즘
• 다음과 같이 3개의 막대와 N개의 원판(Disk)이 있을 때, 원판을 다음의 순서를 지키면서 A에서 C로 옮기는 작업
  • 각 원판의 크기는 모두 다르다.
  • 원판의 크기는 아래에서부터 위로 갈수로 점점 작아진다.

원판이 3개일 때 하노이 탑 알고리즘 과정

① 한 번에 하나의 원판만 이동한다.
② 맨 위에 있는 원판만 이동한다.
③ 크기가 작은 원판 위에 큰 원판을 쌓을 수 없다.

 

• 이 조건에서 다음을 구하는 것이 하노이 탑의 문제가 된다.

① 최소의 이동 횟수로 옮기는 가짓수 ($2^{N} - 1$)
② 최소의 이동 횟수로 옮길 때, 각 원반을 옮기는 순서

 

알고리즘

void hanoi(int N, char from, char tmp, char to) {
    if (N == 1) {
        cout << N << "번 원반을 " << from << "에서 " << to << "로 이동" << '\n';
    }
    else {
       hanoi(N - 1, from, to, tmp);
       cout << N << "번 원반을 " << from << "에서 " << to << "로 이동" << '\n';
       hanoi(N - 1, tmp, from, to);
   }
}

 

사용 예

#include <iostream>
using namespace std;

void hanoi(int N, char from, char tmp, char to) {
    if (N == 1) {
        cout << N << "번 원반을 " << from << "에서 " << to << "로 이동" << '\n';
    }
    else {
       hanoi(N - 1, from, to, tmp);
       cout << N << "번 원반을 " << from << "에서 " << to << "로 이동" << '\n';
       hanoi(N - 1, tmp, from, to);
   }
}

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

1번 원반을 A에서 C로 이동
2번 원반을 A에서 B로 이동
1번 원반을 C에서 B로 이동
3번 원반을 A에서 C로 이동
1번 원반을 B에서 A로 이동
2번 원반을 B에서 C로 이동
1번 원반을 A에서 C로 이동

 

참고 사이트

• https://shoark7.github.io/programming/algorithm/tower-of-hanoi

 

관련 문제

• https://dev-astra.tistory.com/232

[BOJ-11729][C++] 하노이 탑 이동 순서