[C언어] 하노이탑

영화에서 유인원의 지능을 시험할 때 가끔 등장하는 기구..

 

바로 하노이 탑입니다.

(코딩하다보면 침팬치가 더 똑똑하다 생각이 들 수 있습니다)

하노이탑. (출처:위키백과)

규칙은 단순합니다.

 

        - 한 번에 하나의 원판만 옮길 수 있다.

        - 큰 원판이 작은 원판 위에 있어서는 안 된다.

 

위의 규칙을 지키면서, 맨 왼쪽의 기둥을 맨 오른쪽 기둥으로 옮겨주면 됩니다.

 

잘 이해가 안된다면, 아래 Gif를 보면 " 아 이게 그거야~~?! " 하실겁니다.

 

하노이탑의 원리. (출처:위키백과)

 

 

 

그럼 이제 해법에 관해 알아보겠습니다.

 

규칙이 단순한 만큼, 해법도 단순하긴 합니다.

 

        " 원반이 N개일 때, N-1개의 원반을 가운데 기둥으로 옮기고, N번째 원반을 세번째 기둥으로 옮긴다. "

        " 그리고 다시 N-1개의 원반을 세번 째 기둥으로 옮긴다. "

 

말로 써보니 무척 쉽습니다.

 

수식으로도 잠시 알아볼까요?

점화식으로 잘 서술되어있습니다.

 

결국 최단 이동횟수의 합은 메르센 수입니다.

 

프로그래밍 언어로 기술한다고 해서 차이가 크치 않습니다.

(물론 표현하는데에 있어 편의성 차이는 큽니다.)(머쓱)

 

 

알고리즘을 공부하는데에 있어, C언어만큼 디테일하게 이해할 수 있는 언어는 없을것입니다.

C언어로 작성해 보겠습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int hanoi_1(int scale, int from, int temp, int target);
int main(void) {
    unsigned scale;
    printf("<<하노이의 탑>>\n");
    printf("숫자 입력 : ");
    scanf("%d", &scale);
    hanoi_1(scale, 1, 2, 3);//재귀 실행
}
int hanoi_1(int scale, int from, int temp, int target) {
    if (scale == 1) {//원반이 1개 남았을 때 실행
        printf("%d번기둥에서 %d번기둥으로\n", from, target);
    }
    else {
        hanoi_1(scale - 1, from, target, temp);//1번기둥에서 3번기둥을 통해, 2번기둥으로 옮기는 재귀
        printf("%d번기둥에서 %d번기둥으로\n", from, target);
        hanoi_1(scale - 1, temp, from, target);//2번기둥에서 1번기둥을 통해, 3번기둥으로 옮기는 재귀
    }
}
 

줄 별로 나누어서 한번 살펴보겠습니다.

 

우선

5~9 :

main함수입니다. 실행을 하면,

콘솔창에서 하노이탑 원반의 갯수를 입력받아, hanoi_1이라는 함수에

[  원반의 갯수,  1,  2,  3  ]  을 전해줍니다.

1, 2, 3은 각각 원반을 지칭하는데에 쓰입니다.

 

이제 hanoi_1 함수에 대해서 살펴보겠습니다.

 

아까 살펴본 바와 같이, 하노이탑의 원리는 아래와 같습니다.

 

        " 원반이 N개일 때, N-1개의 원반을 가운데 기둥으로 옮기고, N번째 원반을 세번째 기둥으로 옮긴다. "

        " 그리고 다시 N-1개의 원반을 세번 째 기둥으로 옮긴다. "

 

그냥 위의 그 자체입니다.

 

남은 원반의 갯수가 2개 이상이면 else문에서 

        " 원반이 N개일 때, N-1개의 원반을 가운데 기둥으로 옮기고, N번째 원반을 세번째 기둥으로 옮긴다. "

를 실행합니다.

 

남은 원반의 갯수가 1개 이면 if문에 걸려

        " 그리고 다시 N-1개의 원반을 세번 째 기둥으로 옮긴다. "

를 실행합니다.

 

그러다 보면 완성됩니다.

 

.

.

.

.

.

.

.

 

로 끝나면 뭔가 허전하죠?

 

 

횟수를 알아봐야 하지 않을까요?

 

횟수를 알아내는 코드도 한번 작성해 보았습니다.

 

1번 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int hanoi_2(int scale, int from, int temp, int target);
int main(void) {
    unsigned scale;
    printf("<<하노이의 탑>>\n");
    printf("원반개수 : ");
    scanf("%d", &scale);
    printf("총 움직임 횟수 : %d", hanoi_2(scale, 1, 2, 3));//재귀 시행
}
int hanoi_2(int scale, int from, int temp, int target) {
    times = 0;
    if (scale == 1) {//원반이 1개 남았을 때 실행
        printf("%d번기둥에서 %d번기둥으로\n", from, target);
        times++;
    }
    else {
        hanoi_2(scale - 1, from, target, temp);//1번기둥에서 3번기둥을 통해 2번기둥으로 옮기는 재귀
        printf("%d번기둥에서 %d번기둥으로\n", from, target);
        times++;
        hanoi_2(scale - 1, temp, from, target);//2번기둥에서 1번기둥을 통해, 3번기둥으로 옮기는 재귀
    }
    return times;//printf로 출력하면 중간중간에 계속 찍히는데, return을 통해서 최종 return값이 출력될 수 있도록 함.
}

 

2번 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int hanoi_2(int scale, int from, int temp, int target);
int main(void) {
    unsigned scale;
    printf("<<하노이의 탑>>\n");
    printf("원반개수 : ");
    scanf("%d", &scale);
    printf("총 움직임 횟수 : %d", hanoi_2(scale, 1, 2, 3));//재귀 시행
}
int hanoi_2(int scale, int from, int temp, int target) {
    static int times = 0;
    if (scale == 1) {//원반이 1개 남았을 때 실행
        printf("%d번기둥에서 %d번기둥으로\n", from, target);
        times++;
    }
    else {
        hanoi_2(scale - 1, from, target, temp);//1번기둥에서 3번기둥을 통해 2번기둥으로 옮기는 재귀
        printf("%d번기둥에서 %d번기둥으로\n", from, target);
        times++;
        hanoi_2(scale - 1, temp, from, target);//2번기둥에서 1번기둥을 통해, 3번기둥으로 옮기는 재귀
    }
    return times;//printf로 출력하면 중간중간에 계속 찍히는데, return을 통해서 최종 return값이 출력될 수 있도록 함.
}

두 코드를 올려봤습니다.

1번 코드는 안돌아가고, 2번코드는 돌아갑니다.

 

.

.

.

.

.

 

정적 변수를 아십니까?

 

우리는 보통 변수를 선언할 때,

아래와 같이

#include <stdio.h>
int main(void){
    int a = 0;
}
 

선언하곤 합니다.

 

이렇게 되면 auto 형식의 변수로 선언됩니다.

 

auto 변수란, 그 해당 블럭에서 실행될 때 메모리에 들어갔다가, 블럭이 종료되면 변수가 해제되어버립니다.

즉, 하노이탑에서 재귀적으로 호출할 때마다 초기화된다는 뜻입니다.

 

따라서 블럭이 종료되어도 프로그램 전체가 종료될 때까지 버텨주는 변수형식이 필요합니다.

 

이 때 static 변수를 이용하면 유지킬 수 있습니다.

 

 

 

따라서 2번 코드를 통해 전체 횟수를 세어보면,

메르센 수가 나온다. (메르센 수는 a_n = n^2 - 1 이다. 이 수가 소수이면 메르센 소수라고 한다.)

위와 같이 의도한 결과가 나옴을 관찰할 수 있습니다.

 

 

.

.

.

.

.

 

 

위의 방법들은 모두 재귀적 호출을 이용하여 프로그램을 구성해 보았습니다.

 

재귀적 호출 이용이 불가능하다면 어떨까요??

 

그래서 비재귀 호출에 관해서도 알아보겠습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct stack {//C언어 과제이기 때문에, 스택을 구현한 간단한 구조체
    int data;//데이터를 저장
    struct stack* link;//스택의 저장위치 기록
}stack;
stack* top;
stack* createNode();
void push(int data);//데이터 입력 함수 선언
int pop();//데이터 출력 함수 선언
int isEmpty();//스택이 비었는지 확인 함수 선언
 
int main(void) {
    unsigned scale, ch;
    unsigned from = 1, temp = 2, target = 3, times = 0;
    top = createNode();//하노이탑을 담을 스택
    printf("<<하노이의 탑>>\n");
    printf("원반개수 : ");
    scanf_s("%d", &scale);
 
 
    while (1) {
        while (scale > 1) {//scale이 1일 때 종료.
            //from에서 temp를 거쳐 target으로 가기위한 과정
            push(target);push(temp);push(from);
            push(scale);
            scale--;
 
            //temp와 target 서로 역할 교환
            ch = target;
            target = temp;
            temp = ch;
        }
        printf("%d번기둥에서 %d번기둥으로\n", from, target);//원반이 짝수개일 때 첫 target은 2번기둥, 홀수개일 때는 3번기둥
        times++;
        if (!isEmpty()) {//스택이 비어있지 않을 때 실행
            //FILO기 때문에, scale을 먼저 pop
            scale = pop();
            from = pop();temp = pop();target = pop();
            printf("%d번기둥에서 %d번기둥으로\n", from, target);
            times++;
            scale--;
            
            //temp와 from 서로 역할 교환
            ch = from;
            from = temp;
            temp = ch;
 
 
        }
        else {//스택 비우면 종료.
            break;//탈출!
        }
    }
    printf("총 움직임 횟수 : %d", times);
    return 0;
}
 
stack* createNode() {
    stack* p = (stack*)calloc(1, sizeof(stack));//0으로 초기화하면서 메모리 할당
    return p;
}
void push(int data) {
    stack* q = createNode();//노드 생성
    q->data = data;//들어온 데이터를 노드에 입력
    q->link = top->link;//노드의 주소를 최상단 주소로 재지정
    top->link = q;//최상단 
}
int pop() {
    stack* q;
    int result;
    q = top->link;//q는 스택의 최상단
    result = q->data;//최상단의 데이터를 res에 저장
    top->link = q->link;//최상단 주소 재지정
    free(q);//무쓸모 메모리 해제
 
    return result;
}
int isEmpty() {
    return  top->link == NULL;//스택이 비어있을 때 1 반환
}

 

우선 제가 써본 코드 전문입니다.

한 파일 안에 작성해보려고 굉장히 난잡한데, 우선 스택에 관해서 알아보겠습니다.

 

//--------------------------------------------------

스택은 가장 흔한 자료구조입니다.

 

편의점에 알바가 물품 넣는과정, 손님이 빼가는 과정 생각하시면 될것 같습니다.

 

 

FILO라고도 하는데, (First In, Last Out)

들어오는 데이터가 그대로 쌓여

가장 먼저 들어온 데이터는 가장 마지막에 나가게 됩니다.

 

push() : 스택에 데이터를 집어넣습니다.

pop() : 스택의 최상단 데이터를 끄집어냅니다.

isEmpty() : 스택이 비어있는지 프로그램에게 대답합니다. 스택이 손들고 "네!" 또는 "아니오!"로 대답합니다.

//--------------------------------------------------

 

 

비재귀 문법은 뭔가 말로 설명하기 애매한데, 블럭별로 설명해보겠습니다.

일단 데이터는 4개씩 묶어서 진행합니다.(남은 원반갯수, 현재 기둥, 거쳐갈 기둥, 목표 기둥)

 

 

이 블럭은 1번 기둥에서 3번 기둥을 거쳐, 2번기둥까지 N-1개의 원반을 옮기는 경로의 일부를 스택에 쌓아둡니다.

 

 

이 블럭은 N번째 기둥을 1번에서 3번으로 넘기고, 2번기둥에서 3번기둥으로 N-1개의 원반을 옮기면서 출력합니다.

뭔가 비재귀로 구현할 때는, 유튜브에서 많은 갯수의 하노이탑을 풀고있는 영상을 천천히 보면서 코딩하면, 무척 큰 도움이 됩니다.

 

 

뭔가 모르겠는거는 연락주십시오

 

 

행운을 빕니다.