[백준 알고리즘] 11729 하노이 탑 이동 순서

 

 재귀 

: 원래의 자리로 되돌아가거나 되돌아옴

다시 자신의 함수를 호출하는 것을 재귀 함수라고 생각하면 쉽다.

 

재귀 함수를 작성할 때 중요한 것이 2가지가 있다.

1. base case를 만들 것

2. 스택이 줄어들어야 할 것

 

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

11729번: 하노이 탑 이동 순서

풀이방법:    

화면 기록 2021-12-04 오전 9.57.39.mov

1.08MB

 

 

https://www.mathsisfun.com/games/towerofhanoi.html

Play Tower of Hanoi

최소로 움직이기 위해서는 일정한 규칙이 있는데 현실적으로 그걸 우리가 떠올리기는 쉽지 않으니.. 우선 영상을 보고 규칙을 찾아 이해를 해야 한다. 

 

1) 몇번째 원판에서 몇번째 원판으로 이동했는지 출력하는 함수

우선, n=1인 경우와 n=2인 경우는 쉬우니까 직접 머릿속으로 생각해보자.

n=1 인 경우

첫번째 원판에서 마지막 원판으로 이동

 

 

n=2 인 경우

첫번째 원판에서 중간 원판으로 작은 원판 1개 이동

 

첫번째 원판에서 마지막 원판으로 밑판 원판 1개 이동

 

두번째 원판에서 마지막 원판으로 작은 원판 1개 이동

 

 

n=3 인 경우

1) 제일 밑 원판 빼고 n-1개를 첫번째 원판에서 중간 원판으로 이동== n=2인 경우인데 첫번째 원판에서 중간 원판으로 이동

 

 

 

2) 제일 밑 원판을 첫번째 원판에서 마지막 원판으로 이동

 

3) n-1개를 두번째 원판에서 마지막 원판으로 이동

 

== n=2인 경우인데 두번째 원판에서 마지막 원판으로 이동

 

 

n=4 인 경우

1) 제일 밑 원판 빼고 n-1개를 첫번째 원판에서 중간 원판으로 이동

== n=3인 경우인데 첫번째 원판에서 중간 원판으로 이동

 

 

 

2) 제일 밑 원판을 첫번째 원판에서 마지막 원판으로 이동

3) n-1개를 두번째 원판에서 마지막 원판으로 이동

== n=3인 경우인데 두번째 원판에서 마지막 원판으로 이동

 

...

 

 

n인 경우

1) 제일 밑 원판 빼고 n-1개를 첫번째 원판에서 중간 원판으로 이동

2) 제일 밑 원판을 첫번째 원판에서 마지막 원판으로 이동

3) n-1개를 두번째 원판에서 마지막 원판으로 이동

 

 

 

재귀 함수로 작성

 

void hanoitop(int n, char hano1, char hano2, char hano3){ //n은 원판의 수
    if(n == 1){
        cout << hano1 << " " << hano3<<"\n";
    }else{
        hanoitop(n-1,hano1,hano3,hano2);
        cout << hano1 << " " << hano3<<"\n";
        hanoitop(n-1,hano2,hano1,hano3);
    }
}

 

 

1. base case를 만들 것

f(n == 1){
//// n==1일 경우에는 첫번째 원판에서 마지막 원판으로 이동
        cout << hano1 << " " << hano3<<"\n";
    }

--> 프로그램이 끝이 나야하니까 계속적인 호출을 무한 반복을 해서는 안된다. 호출의 끝을 만들어줘야 한다 !

 

2. 스택이 줄어들어야 할 것

else{
//1) 제일 밑 원판 빼고 n-1개를 첫번째 원판에서 중간 원판으로 이동 (hano1(첫번째 원판)에서 hano2(중간 원판)으로 이동)
        hanoitop(n-1,hano1,hano3,hano2);
//2) 제일 밑 원판을 첫번째 원판에서 마지막 원판으로 이동했음을 출력
        cout << hano1 << " " << hano3<<"\n";
//3) n-1개를 두번째 원판에서 마지막 원판으로 이동(hano2(두번째 원판)에서 hano3(마지막 원판)으로 이동)
        hanoitop(n-1,hano2,hano1,hano3);
    }

 

 

 

2) 하노이탑의 이동 횟수를 출력하는 함수

n=1 일 때 1회 이동

 

n=2 일 때 3회 이동

n=3 일 때 7회 이동

n=4 일 때 15회 이동

n=5 일 때 31회 이동

 

n이 1씩 증가할 때마다 +2, +4, +8, +16이 되는 것을 볼 수 있다.

다시 말해,

n=1 일 때 1회 = 2^0

n=2 일 때 3회 = 2^0+ 2^1

n=3 일 때 7회 = 2^0+ 2^1 + 2^2

n=4 일 때 15회 = 2^0+ 2^1 + 2^2 +2^3

n=5 일 때 31회 = 2^0+ 2^1 + 2^2 +2^3 + 2^4

...

n일 때 2^0+ 2^1 + 2^2 +2^3 + ... + 2^(n-1) -> 등비 수열의 합

 

 

등비 수열의 합

즉,  2^0+ 2^1 + 2^2 +2^3 + ... + 2^(n-1)은 a가 1, r이 2이기 때문에 Sn = (2^n-1)/(2-1) = 2^n-1이다.

등비수열의 합 증명 방법은 다음 사이트에 잘 정리되어 있다!

 

https://mathbang.net/612

등비수열의 합, 등비수열의 합 공식

 

따라서 하노이탑의 이동 횟수를 출력하는 함수는 다음과 같은 코드가 나온다.

void hanoitop_count(int n){
    cout << (int)pow(2,n)-1<<"\n";
}

 

하노이탑의 이동 횟수를 출력할 때 pow를 사용하기 위해서는

1. <math.h> 헤더 파일을 include 해야 한다.

2. pow는 double형을 반환하기 때문에 int형으로 형 변환을 해야한다.

 

 

작성한 코드는 다음과 같다 

#include <iostream>
#include <math.h>
using namespace std;

void hanoitop_count(int n){
    cout << (int)pow(2,n)-1<<"\n";
}


void hanoitop(int n, char hano1, char hano2, char hano3){ //n은 원판의 수
    if(n == 1){
        cout << hano1 << " " << hano3<<"\n";
    }else{
        hanoitop(n-1,hano1,hano3,hano2);
        cout << hano1 << " " << hano3<<"\n";
        hanoitop(n-1,hano2,hano1,hano3);
    }
}

int main() {
    int N;
    cin >> N;
    hanoitop_count(N);
    hanoitop(N, '1','2','3');
    return 0;
}

성공한 사진!    

 

 MEMO  

재귀하면 제일 먼저 떠오르는 하노이 탑!! 재귀.. 이제 제법 친해졌을지도?