[C언어] 백준 11729번 : 하노이 탑 이동 순서 <Silver 1>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

Code

---

#include <stdio.h>
#include <math.h>

 

// 하노이탑 이동 규칙을 이용한 재귀함수
void hanoi(int N, int one, int two, int three ){
    if(N == 1)
        printf("%d %d\n", one, three);
    else{
        hanoi(N-1, one, three, two);
        printf("%d %d\n", one, three);
        hanoi(N-1, two, one, three);
    }
}

int main() {
    int num = 0; // 원판의 갯수
    int result = 0; // 총 이동 횟수 == 정답
    int first = 1; // 하노이의 첫번째 기둥
    int second = 2; // 하노이의 두번째 기둥
    int third = 3; // 하노이의 세번째 기둥
    
    scanf("%d", &num);

 

    // 하노이의 총 이동 횟수
    result = pow(2, num) - 1;

    printf("%d\n", result);

    hanoi(num, first, second, third);
    
    return 0;
}

---

Code 필수 요소

1. 하노이탑의 이동 규칙

2. 재귀함수를 이용한 풀이법

 

이것만 생각해내면 절반은 끝났다.

 

// 하노이탑 이동 규칙을 이용한 재귀함수

이것에 대한 설명을 하기 전에, 재귀함수에 대해서 간단하게 설명하겠다. 말 그대로 함수에서 함수 자신을 호출하는 것을 말한다.

그래서 이런 저런 편함이 있지만, 반드시 해야하는 주의점으로는 루프 탈출을 위한 장치가 있어야한다. 그렇다면 왜 필요한가? 당연히 함수에서 함수 자신을 호출하는데 탈출을 위한 장치가 없다면 무한대로 자신을 호출하기때문이다. 쉽게 말하면 while(1)을 해두고 내부에 break를 넣지 않은것과 똑같은 행동이다.

 

그렇다면 하노이탑의 이동 방법은 왜 재귀함수를 이용해야 하는가? 원판이 4개일때와 3개일때를 예시로 들어보자.4개를 옮길때 순서대로 3개가 쌓여있는 것을 만들고 남은 하나를 원하는 위치에 옮기는 방식을 사용한다. 그 후 쌓여있는 3개를 나머지 하나 위에 순서대로 쌓는 방법을 사용한다. 자, 방금 말한거에서 이유가 나왔다. 처음에 3개를 옮기고, 옮겨둔 하나 위에 3개를 옮긴다. 원판 3개일때와 다른점은 맨 밑의 하나를 움직인다는 점을 제외하면 동일하다. 그렇다면 원판이 3개일때와 2개일때, 5개일때와 4개일때 또한 마찬가지다. 그렇기 때문에 재귀함수를 이용해서 동일한 작업을 편리하게 하는 것이다.

 

if(N == 1)
        printf("%d %d\n", one, three);

 

이게 재귀함수의 탈출 조건이다. N은 원판의 갯수를 나타내기 때문에 원판이 하나 남았기때문에 그때의 결과를 출력하고 탈출한다.

 

else{
        hanoi(N-1, one, three, two);
        printf("%d %d\n", one, three);
        hanoi(N-1, two, one, three);
    }

 

이건 하노이의 이동 규칙이다. 어떻게 이렇게 작성했냐 하면 나도 이러고싶지 않았다. 정말 모르겠어서 하나하나 다 적어가면서 알아냈다...

 

// 하노이의 총 이동 횟수

갑자기 result = pow(2, num) - 1 라는 문장으로 이동 횟수를 계산했는데, 공식이다. 외워야 하는건 아니고 난 이런건 구글에 그때그때 검색해서 사용한다. 물론 재귀함수 내부에 count하는 변수를 넣어서 계산해도 수를 구할 순 있을거다. 하지만 문제 조건에 총 이동 횟수를 먼저 출력하라 했기때문에 공식을 사용했다.

 

이 문제는 하노이의 이동 규칙을 알아내는게 제일 귀찮으면서 어려웠고, 재귀함수 자체를 떠올리는데 어려웠다. 물론 문제 자체는 백준 난이도에 비하면 쉬웠다.

 

 

-꿑-