하노이의 탑 알고리즘 공식

11729번: 하노이 탑 이동 순서

백준에 있었던 하노이의 탑 이동 순서 문제.

공식만 알면 쉽게 풀 수 있는 문제인 개념이므로 개념을 정리해 보겠다.

 

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다. 한 번에 한개의 원판만 옮길 수 있다. 큰 원판이 작은 원판 위에 있어서는 안 된다. 하노이의 탑의 원리(애니메이션) 하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 그렇기 때문에 프로그래밍 수업에서 알고리즘 예제로 많이 사용한다. 일반적으로 원판이 n개 일 때, 2^n -1번의 이동으로 원판을 모두 옮길 수 있다(2^n − 1는 메르센 수라고 부른다). 출처 : 위키피디아 - https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91

 

우선 하노이의 탑에서 원판이 n개일 때 원판들의 이동횟수는 다음과 같다. 

1. n = 1, 그냥 하나만 옮기므로 1번
2. n = 2, 3번
3. n = 3, 7번
4. n = 5, 15번

즉, 이동횟수에 대한 점화식은

An = 2*A(n-1) + 1이라고 할 수 있다.

물론 위키피디아 설명에서 말한 것 처럼, 2^n - 1로 생각해도 상관없다. 둘 다 같은 뜻이다.

 

이동횟수는 알았는데 이동경로는 어떻게 알 수 있을까? 한번 그려보고 규칙을 찾아보자.

n = 2일 때,

1. 1 -> 2
2. 1 -> 3
3. 2 -> 3

n = 3일 때,

1. 1 -> 3
2. 1 -> 2
3. 3 -> 2
4. 1 -> 3
5. 2 -> 1
6. 2 -> 3
7. 1 -> 3

n = 4일 때,

1. 1 -> 2
2. 1 -> 3
3. 2 -> 3
4. 1 -> 2
5. 3 -> 1
6. 3 -> 2
7. 1 -> 2
8. 1 -> 3
9. 2 -> 3
10. 2 -> 1
11. 3 -> 1
12. 2 -> 3
13. 1 -> 2
14. 1 -> 3
15. 2 -> 3

이다.

사실 위 관계로는 내 경우에는 유추하기가 쉽지 않았다.

찾아보니 다음과 같은 매커니즘이였다.

1. A -> B로 n-1개의 원판을 옮긴다.
2. n-1개가 다 옮겨졌다면 A -> C로 1개의 원판을 옮겨놓는다.
3. 후에 B -> C로 다시 n - 1개의 원판을 옮긴다.

 

위키피디아에서 예시 코드를 확인해 보았다.

#include <cstdio>  using namespace std;  void move(int from, int to) {       cout << from << " -> " << to << '\n';  }  void hanoi(int n, int from, int by, int to) {       if(n == 0) return;       hanoi(n - 1, from, to, by);       move(from, to);       hanoi(n - 1, by, from, to);  } 출처 : 위키피디아 - https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91

위 코드가 예시 코드이다.

void go(int cnt, int from, int by, int to) {     if (cnt == 1) {         cout << from << " " << to << "\n"; // 만일 원판이 한 개만 있을 경우에는 바로 3번으로 옮긴다.     }     else {         go(cnt - 1, from, to, by); // 1번 -> 2번으로 n-1개를 옮기기 위한 재귀함수.         cout << from << " " << to << "\n";         go(cnt - 1, by, from, to); // 2번 -> 3번으로 n-1개를 옮기기 위한 재귀함수.     } }

백문 문제에 맞게 다음과 같이 바꾸었고 거의 흡사하다.

예시로 go(3, 1, 2, 3)을 호출한다면

• go(2, 1, 3, 2) -> go(1, 1, 2, 3) -> "1 3" -> "1 2" -> go(1, 3, 1, 2) -> "3 2" -> "1 3" -> go(2, 2, 1, 3)
• -> go(1, 2, 3, 1) -> "2 1" -> "2 3" -> go(1, 1, 2, 3) -> "1 3"

의 순서로 진행이 된다.

 

하노이 탑 공식은 유명한 공식이므로 한번 정리해 보았다.