[C] 하노이의 탑 구현하기 (재귀, 비재귀)

[C] 하노이의 탑 구현하기 (재귀, 비재귀)

하노이의 탑 게임은 세 개의 기둥과 서로 다른 크기의 N개의 원반으로 구성된다.

이 원반들은 세 개의 기둥 중의 하나에 반드시 꽂혀 있어야 하며, 자신보다 작은 원반 위에는 그 원반을 놓을 수 없다.

즉 원반은 아래에 가장 큰 것이 와야 하며 위로 갈 수록 원반은 작아져야 한다.

문제는 기둥 1에 N개의 원반이 모두 꽂혀 있는 것에서 시작한다. 물론 이 원반들은 크기순으로 배열되어 있다.

이 원반을 기둥 2를 이용하여 기둥 3으로 모두 옮기는 것이다.

ex > N == 3

1. 기둥 1의 원반을 기둥 3으로 옮긴다.

2. 기둥 1의 원반을 기둥 2로 옮긴다.

3. 기둥 3의 원반을 기둥 2로 옮긴다.

4. 기둥 1의 원반을 기둥 3으로 옮긴다.

5. 기둥 2의 원반을 기둥 1로 옮긴다.

6. 기둥 2의 원반을 기둥 3으로 옮긴다.

7. 기둥 1의 원반을 기둥 3으로 옮긴다.

하노이 탑의 문제 해결 방법

1. 기둥 1에서 N-1개의 원반을 기둥 2로 옮긴다.

2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다.

3. 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.

// 원반을 from에서 to로 옮긴다. void move(int from, int to){     printf("\nMove from %d to %d", from, to); } // n개의 원반을 from 에서 by를 거쳐 to로 옮긴다. void hanoi(int n, int from, int by, int to){     if (n == 1)         move(from, to);     else{         hanoi(n - 1, from, to, by);    // 1번  N-1개의 원반을 기둥3을 거쳐 2로 옮긴다.         move(from, to);                // 2번 기둥 1에서 1개의 원반을 기둥 3으롱 롬긴다.         hanoi(n - 1, by, from, to);    // 3번 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.     } }

* 비 재귀로 변환

위의 방법은 두번의 재귀 함수와 실제 동작(move)가 가운데 있는 형태이다.

이것을 스택을 이용한 비재귀 방법으로 아래와 같이 변환한다.

// 하노이의 탑 비재귀로 변환 void nr_hanoi(int n, int from, int by, int to){     init_stack();     while (1){         while (n > 1){             push(to);    // 인자리스트 푸쉬             push(by);             push(from);             push(n);             n--;        // 인자리스트 변경 1             push(to);    // to 와 by를 교환하기 위해 임시로 저장             to = by;             by = pop();         }         move(from, to);        // 재귀의 마지막 종료 처리         if (!is_stack_empty()){             n = pop();             from = pop();             by = pop();             to = pop();             move(from, to);        // 실제 이동 작업             n--;        // 인자리스트 변경 2             push(from);             from = by;             by = pop();         }         else{             break;         }     } }

* 전체 소스코드

#include <stdio.h> // 하노이의 탑 // 1. 기둥 1에서 N-1개의 원반을 기둥 2로 옮긴다. // 2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다. // 3. 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다. // 원반을 from에서 to로 옮긴다. void move(int from, int to){     printf("\nMove from %d to %d", from, to); } // n개의 원반을 from 에서 by를 거쳐 to로 옮긴다. void hanoi(int n, int from, int by, int to){     if (n == 1)         move(from, to);     else{         hanoi(n - 1, from, to, by);    // 1번  N-1개의 원반을 기둥3을 거쳐 2로 옮긴다.         move(from, to);                // 2번 기둥 1에서 1개의 원반을 기둥 3으롱 롬긴다.         hanoi(n - 1, by, from, to);    // 3번 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.     } } // 비재귀에 사용하기 위한 스택 #define MAX 100 int stack[MAX];        // 스택의 긴  통 int top;            // 스택의 상단 void init_stack(void){     top = -1; } int push(int t){     if (top >= MAX - 1){         printf("\n    Stack overflow.");         return -1;     }     stack[++top] = t;     return t; } int pop(void){     if (top < 0){         printf("\n   Stack underflow.");         return -1;     }     return stack[top--]; } int is_stack_empty(){     return (top > -1) ? 0 : 1; } // 하노이의 탑 비재귀로 변환 void nr_hanoi(int n, int from, int by, int to){     init_stack();     while (1){         while (n > 1){             push(to);    // 인자리스트 푸쉬             push(by);             push(from);             push(n);             n--;        // 인자리스트 변경 1             push(to);    // to 와 by를 교환하기 위해 임시로 저장             to = by;             by = pop();         }         move(from, to);        // 재귀의 마지막 종료 처리         if (!is_stack_empty()){             n = pop();             from = pop();             by = pop();             to = pop();             move(from, to);        // 실제 이동 작업             n--;        // 인자리스트 변경 2             push(from);             from = by;             by = pop();         }         else{             break;         }     } } void main(void){     int i = 5;     hanoi(i, 1, 2, 3);     printf("\n\n\nNon Recursive Hanoi \n");     nr_hanoi(i, 1, 2, 3);     return 0; }

출처: https://hyeonstorage.tistory.com/355?category=622873 [개발이 하고 싶어요]