하노이탑 알고리즘 Tower of Hanoi - 박스여우

안녕하세요 박스여우입니다.

Algorithm

이번에는 선생님이 장난으로 내 주신 과제. 하노이탑에 대해 알아보도록 하겠습니다.

 

우선 하노이탑의 해결 과정을 알아내기 위해 Youtube의 여러 하노이탑 영상들을 찾아봤습니다.

 

 

저는 위의 두 영상을 보고 해결되는 규칙을 찾아냈습니다.

위의 하노이탑 해결 과정에서 반복적으로 움직이는 블럭을 하나 찾아봅시다.

 

만약 위의 영상을 보고도 반복적인 모습을 찾지 못했다면 아래 영상을 통해 다시한번 살펴봅시다.

 

 

위의 영상에서 가장 작은 블럭의 움직임을 자세히 살펴보면,

반복적으로 움직이고 있다는 모습이 보일 것 입니다.

 

 가장 작은 블럭은 1번기둥, 2번기둥, 3번기둥 순으로 반복적으로 움직이고 있고,

가장 작은 블럭이 한번 움직이면 가장 작은 블럭이 없는 다른 기둥의 둘중 하나의 블럭이 움직입니다.

이 규칙을 사용해서 하노이탑을 해결하는 알고리즘을 작성할 수 있습니다.

알고리즘에 대한 내용을 다룰때 항상 말씀드리는 점이 있는데,

스스로 해결할 수 있는 능력을 향상시켜야 합니다.

스크롤을 조금만 아래로 내리시면 제가 작성한 알고리즘이 나오지만, 제 알고리즘을 보시기 전에

먼저 혼자 스스로 해결해 보시는게 중요합니다. 그래야 문제해결 능력이 향상됩니다.

해결 과정

저는 가장 작은 블럭을 Lock으로 생각했습니다.

마치 시분할 시스템과 비슷하게 각 기둥에 공평하게 한번씩 돌아가면서 Lock을 걸어주는 역할을 하는 것 이죠.

Lock이 걸린 기둥을 제외한 나머지 두 기둥의 가장 위의 블럭들을 비교해서

더 작은 블럭이 큰 블럭위로 이동하게 만드는 것 입니다.

void Next(){
    int target;
        if (tall % 2 == 0 && first == 2) target = 0;
        else if (tall % 2 == 0)target = first + 1;
        else if (first == 0) target = 2;
        else target = first -1;
    arr[target][++getTop[target]] = arr[first][getTop[first]];
    arr[first][getTop[first]--] = 0;
    first = target; 
}

일단 규칙적으로 작은 블럭을 움직이는 코드입니다.

만약 블럭의 개수가 짝수이면 1번, 2번, 3번 순으로 움직이고,

홀수이면 3, 2, 1번 순으로 움직입니다.

제가 8, 9단 하노이탑 해결 과정 두 개를 보여드린 이유 입니다.

블럭의 개수가 홀수일때, 짝수일때 가장 작은 블럭의 이동방향이 반대입니다.

가장 작은 블럭을 해결했으니, 이제 나은 두 기둥의 블럭을 이동시켜야 합니다.

void subSort(int i, int b, int c){
    if (getTop[b] < 0 || arr[i][getTop[i]] < arr[b][getTop[b]]){
        arr[b][++getTop[b]] = arr[i][getTop[i]];
        arr[i][getTop[i]--] = 0;
        check = 1;
    }
    else if (getTop[c] < 0 || arr[i][getTop[i]] < arr[c][getTop[c]]){
        arr[c][++getTop[c]] = arr[i][getTop[i]];
        arr[i][getTop[i]--] = 0;
        check = 1;
    }
}
void sorting(){
    while (check != 0){
        check = 0;
        print();
        Next();
        print();
        for (int i = 0; check != 1 && i < 3; i++){
            if (i == first || getTop[i] == -1 || arr[i][getTop[i]] == 0)continue;
            if (i == 2) subSort(i, 0, 1);
            else if (i == 1) subSort(i, 2, 0);
            else if (i == 0) subSort(i, 1, 2);
        }
    }
}

남은 두 기둥들에 대해 연산을 하는 과정입니다.

가장 작은 블럭의 위치를 나타내는 변수가 first이고, for문을 통해 0~2까지의 배열로 이루어진 기둥을 검사합니다.

만약 검사하고자 하는 기둥에 가장작은 블럭이 있으면 넘어가고, 없다면 남은 두 기둥을 대상으로 연산을 합니다.

아래는 전체 소스코드 입니다.

#include <stdio.h>
#include <Windows.h>
#pragma warning(disable:4996)
 
int **arr, *getTop, tall, hole = 3, first = 0, check = 1;
void Next(){
    int target;
        if (tall % 2 == 0 && first == 2) target = 0;
        else if (tall % 2 == 0)target = first + 1;
        else if (first == 0) target = 2;
        else target = first -1;
    arr[target][++getTop[target]] = arr[first][getTop[first]];
    arr[first][getTop[first]--] = 0;
    first = target; 
}
void print(){
    system("cls");
    for (int j = tall - 1; j >= 0; j--, printf("\n")){
        for (int i = 0; i < 3; i++, printf("")){
            if (arr[i][j] < 0)arr[i][j] = 0;
            else{
                for (int k = 0; k < tall - arr[i][j]; k++)printf(" ");
                for (int k = 0; k < arr[i][j]; k++)printf("〓");
                for (int k = 0; k < tall - arr[i][j]; k++)printf(" ");
            }
        }
    }
    Sleep(1000);
}
void subSort(int i, int b, int c){
    if (getTop[b] < 0 || arr[i][getTop[i]] < arr[b][getTop[b]]){
        arr[b][++getTop[b]] = arr[i][getTop[i]];
        arr[i][getTop[i]--] = 0;
        check = 1;
    }
    else if (getTop[c] < 0 || arr[i][getTop[i]] < arr[c][getTop[c]]){
        arr[c][++getTop[c]] = arr[i][getTop[i]];
        arr[i][getTop[i]--] = 0;
        check = 1;
    }
}
void sorting(){
    while (check != 0){
        check = 0;
        print();
        Next();
        print();
        for (int i = 0; check != 1 && i < 3; i++){
            if (i == first || getTop[i] == -1 || arr[i][getTop[i]] == 0)continue;
            if (i == 2) subSort(i, 0, 1);
            else if (i == 1) subSort(i, 2, 0);
            else if (i == 0) subSort(i, 1, 2);
        }
    }
}
void main(){
    puts("단을 입력해 주세요 : ");
    scanf("%d", &tall);
    arr = (int*)malloc(sizeof(int)*hole);
    for (int i = 0; i < hole; i++) arr[i] = (int*)malloc(sizeof(int)*tall + 1);
    for (int i = 0; i < tall; i++) arr[0][i] = tall - i;
    getTop = (int*)malloc(sizeof(int)*hole);
    getTop[0] = tall - 1, getTop[1] = -1, getTop[2] = -1;
    sorting();
}