자료구조 C언어 (Recursion 함수 와 동적할당)

---

개요

 

학교 과제하느라 바빠서 업로드 못했지만 이번에는 좋은 프로그램 개발자가 되기 위해서는 반드시 필요한 Recursion 함수에 대해서 알아보도록 하겠다.

 

---

설명

 

Recursion 함수의 꽃은 개발자라면 한번쯤 봤을법한 Hanoi Tower에 관한 구현이다. 책에서는 그냥 뭐가 어디로 이동되었다 printf()문으로만 이루어져 있지만 진짜로 Recursion function을 이해하기 위해 다음 아래와 같이 작성하였다.

 

---

코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int i, j;
int n_tmp;//원반개수
int x, y;

int hanoi_tower(int n, int from, int tmp, int to, int** ST)
{

    FILE* fp = fopen("hanoi_result.txt", "a+");
    int CNT[3] = { 0, };

    if (n == 1)
    {
        fprintf(fp, "Disk 1 is moved from pole %d to pole %d\n", from, to);
        //n값의 위치를 찾음
        for (i = 0; i < 3; i++)
        {
            for (j = 0; j < n_tmp; j++)
            {
                if (ST[i][j] == n)
                    x = i, y = j;
            }
        }
        //0일때 값 넣어줌
        for (j = 0; j < n_tmp; j++)
        {
            if (ST[to - 1][j] == 0)
            {
                ST[to - 1][j] = ST[x][y];
                ST[x][y] = 0;
            }
        }
        //원반개수체크
        for (i = 0; i < 3; i++)
        {
            for (j = 0; j < n_tmp; j++)
            {
                if (ST[i][j] != 0)
                    CNT[i]++;
            }
        }
        //출력
        for (i = 0; i < 3; i++)
        {
            for (j = 0; j < n_tmp; j++)
            {
                printf("%d ", ST[i][j]);
            }
            printf("___%d\n", CNT[i]);
        }
        printf("ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ\n");
    }
    else
    {
        hanoi_tower(n - 1, from, to, tmp, ST);
        fprintf(fp, "Disk %d is moved from pole %d to pole %d\n", n, from, to);
        for (i = 0; i < 3; i++)
        {
            for (j = 0; j < n_tmp; j++)
            {
                if (ST[i][j] == n)
                    x = i, y = j;
            }
        }
        for (j = 0; j < n_tmp; j++)
        {
            if (ST[to - 1][j] == 0)
            {
                ST[to - 1][j] = ST[x][y];
                ST[x][y] = 0;
            }
        }
        for (i = 0; i < 3; i++)
        {
            for (j = 0; j < n_tmp; j++)
            {
                if (ST[i][j] != 0)
                    CNT[i]++;
            }
        }
        for (i = 0; i < 3; i++)
        {
            for (j = 0; j < n_tmp; j++)
            {
                printf("%d ", ST[i][j]);
            }
            printf("___%d\n", CNT[i]);
        }
        printf("ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ\n");
        hanoi_tower(n - 1, tmp, from, to, ST);
    }
}
int main()
{
    int n;
    int** ST;
    int tmp;
    int CNT[3] = { 0, };

    //-3 개의 pole 에 꽃혀 있는 disk 의 상황은 2차원 배열 ST 에 가지고 있게 한다.
    //프로그램이 시작하면  먼저 원반의 총수  n 를 키보드에서 받게 한다.
    printf("원반의 개수 입력: ");
    scanf("%d", &n);

    ST = (int**)malloc(sizeof(int*) * 3);
    for (i = 0; i < 3; i++) {
        ST[i] = (int*)malloc(sizeof(int) * n);
    }

    //초기값 설정
    n_tmp = n;
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (i == 0)
                ST[i][j] = n_tmp--;
            else
                ST[i][j] = 0;
        }
    }

    n_tmp = n;
    CNT[0] = n;

    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < n; j++)
        {
            printf("%d ", ST[i][j]);
        }
        printf("___%d\n", CNT[i]);
    }
    printf("ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ\n");


    hanoi_tower(n, 1, 2, 3, ST);

    return 0;

}

 

 

이 프로그램을 실행하고 나면 같은 솔루션 디렉터리에 txt파일이 만들어져 이동경로가 어떻게 되는지 기술이 되어있다.

사실 이번에 하면서 느낀거는 간단해 보이지만 상당히 고생했다 ㅠ .. 이미 한번 이해했었던 Hanoi Tower 였는데 이런식으로 코딩할려고 하니까 상당히 막히는 부분이 많았다 ㅠㅠ 그래서 알고리즘을 더욱 공부해야 겠다고 느끼며 백준 사이트에서 알고리즘을 공부하고 업로디 하는 학습도 해야겠다 ㅠ

 

---

실행화면

 

실행화면

 

---