하노이 탑(The Tower of Hanoi)은
3개의 막대 중에서 막대 하나에 쌓여 있는 n개의 원판을 다른쪽 막대로 옮기는 게임이다.
단, 아래의 규칙을 지켜야 한다.
1. 한번에 하나의 원판만 이동한다.
2. 맨 위에 있는 원판만 이동한다.
3. 크기가 작은 원판위에 큰 원판을 쌓을 수 없다.
n개의 원판을 옮기기 위해서는 먼저 임시 막대에 n-1개의 원판을 옮긴 후
처음 막대에 남아있는 맨 밑 원판을 목적지 막대에 옮기는 것을 반복한다.
그러고나면 원래 원판이 쌓여있던 막대는 빈 막대가 되고 임시 막대에는 n-1개의 원판이,
목적지 막대에는 가장 큰 원판이 하나 놓여있게 된다.
임시 막대에 있는 원판의 개수를 n으로 다시 설정하고 n-1개의 원판을 원래 원판이 있었던 첫막대에
옮긴다. 임시 막대에 남아있는 원판 하나를 목적지 막대에 옮긴다.
임시막대를 번갈아가면서 계속 반복하면
.
.
.
결국 임시 막대에는 제일 작은 원판 하나가 남게 되고, 이 원판을 옮기면
목적지 막대에 원판이 모두 쌓이게 된다.
와! 그러면 엄청 쉬운거 아닌가요?
프로그래밍을 처음 접하는 사람이면 하노이 탑이 첫 난관일 수도 있다.
하나하나 짚어가면서 생각해보면 쉬우니까 포기하지 말고 열심히 해보자.
n개의 원판을 옮기는데 드는 횟수는 (2^n)-1 번.
시간복잡도는 O(2^n)
#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to) {
if (n == 1) {
printf("No.1 disk moves from %c to %c\n", from, to);
}
else {
hanoi_tower(n - 1, from, to, tmp);
printf("No.%d disk moves from %c to %c\n", n, from, to);
hanoi_tower(n - 1, tmp, from, to);
}
}
int main() {
hanoi_tower(3,'A','B','C');
return 0;
}
하노이 탑의 함수를 만들어줬다.
n은 원판의 갯수고, from은 첫 막대, tmp는 임시 막대, to는 목적지 막대이다.
만약 원판이 하나면 옮기는 것이다.
from에서 to로.
어? 그럼 1은 무조건 from에서 to로 가는게 아닌가요?
코드로만 보면 그렇게 보이겠지만 하노이 탑 함수 안에 들어있는 재귀함수를 보라.
7번째 줄을 보면 from,to,tmp 따위의 막대들의 위치가 바뀌어 인자로 들어간다.
그러면 tmp 위치에는 to가 들어가고 to 위치에는 tmp가 들어간다.
무슨 소리인가 싶겠지만
1이 있는 막대의 위치에 따라서 1이 A 기둥에도 B 기둥에도 C 기둥에도
어디든지 갈 수 있다는 소리다.
main함수 안에 적어놓은 하노이탑 함수의 첫번째 인자의 숫자를 수정하면
다른 개수의 원판이 옮겨지는 과정도 볼 수 있으니 참고하도록 하자.
원판 개수가 3개일 때를 예로 들어 하나하나 따라가 보자면 아래의 사진과 같다.
아래의 설명을 이해하기 쉽게 들여쓰기로 작성했으니 pc버전에서 보길 권장한다.
원판이 3개일 때 hanoi_tower 함수가 작동하는 과정을 볼 수 있다.
hanoi_tower(3,A,B,C)함수가 선언되었다.
else 문에 걸려서 n-1한 후 hanoi_tower(2,A,C,B)로 가준다.
이 함수는 임시 기둥으로 원판을 다 옮겨준다.
여기서 else문이 걸려서 hanoi_tower(1,A,B,C)로 간다.
1일땐 from에서 to로 옮겨주므로
1을 A->C
다시 hanoi_tower(2,A,C,B)로 돌아가 다음 명령을 실행한다.
n과 from to를 출력하는 것이다.
그러면 2번째 원판이 A에서 B로 옮겨진다.
2를 A->B
그 다음 명령문을 실행한다.
hanoi_tower(1,C,A,B)로 간다.
n은 1이므로 C->B
이제 hanoi_tower(2,A,C,B)는 끝났다. hanoi_tower(3,A,B,C)로 돌아간다.
hanoi_tower(3,A,B,C)의 두번째 명령문을 실행한다.
3을 A->C
hanoi_tower(3,A,B,C)의 세번째 명령문을 실행한다.
hanoi_tower(2,B,A,C)에서 else문에 걸린다.
hanoi_tower(1,B,C,A)가 되면 1을 B->A
다시 돌아와서 hanoi_tower(2,B,A,C)의 두번째 명령문을 실행한다.
2 B->C
hanoi_tower(2,B,A,C)의 세번째 명령문이 실행된다.
hanoi_tower(1,A,B,C)
1 A->C
<함수 종료>
코드를 작성한 후에 어떻게 작동하는지 이해가 간다면 잘 따라잡은 것이다.
비교적 쉬웠던 피보나치 수열보다는 조금 복잡할지는 몰라도 순환을 이해하기 위한 기초 중의 기초니까
기반을 잘 다졌으면 좋겠다.
'Computer Science > Algorithm' 카테고리의 다른 글
| [Algorithm] A* 알고리즘 (0) | 2024.10.06 |
|---|