[백준 11729] 하노이 탑 옮기기(재귀) 문제해석 / 풀이 / 코드

하노이 탑 문제

시작 기둥, 보조 기둥, 목적 기둥 3개로 나눠 놓았을 때,
시작 기둥에 있는 n개의 원판을 목적 기둥으로 옮기는 게임이다.

조건

1. 한번에 하나만 옮기고
2. 큰 원판이 작은 원판 위에 있으면 안된다.

관찰

결국에는 가장 큰 n번째 원판이 목적기둥으로 이동해야 하고,
그 중간 과정에서, n-1개의 원판은 보조기둥에 위치한다.

즉 정리하면, n개의 원판을 시작->목적으로 옮기는 작업은 아래 세 과정으로 요약된다.

1. n-1개의 원판을 시작->보조로 옮기기,
2. 원판n을 시작->목적 옮기기,
3. n-1개의 원판을 보조->목적으로 옮기기

수식으로 이해

f(n)을 n개의 탑을 옮기는 데 필요한 이동횟수라 하자.
위 관찰 과정에서 확인한대로 식을 정리하면,
f(n) = 2*f(n-1) + 1이 된다.
n-1개의 원판을 두 번 옮기는것과 n번째 원판을 한 번 옮기는 것으로 분해한다는 뜻이다.

f(1)=1이고, f(2)=3이므로 원판의 이동횟수는 f(n)=pow(2,n)-1의 형태를 가진다.

소스코드

#include<cstdio>
#include<cmath>
void hanoi(int disks, int start, int sub, int end) { // start -> end로 옮기는 게 목적
    if(disks==1) { // 1일 때 그냥 이동
        printf("\n%d %d", start, end);
        return;
    }
    hanoi(disks-1, start, end, sub); // n-1을 start -> sub로 이동
    printf("\n%d %d", start, end); // start -> end 옮긴다.
    hanoi(disks-1, sub, start, end); // n1개를 다시 sub -> end로 이동
}
int main() {
    int n;
    scanf("%d", &n);

    printf("%d", (int)pow(2,n)-1); // 이동횟수는 그냥 구할 수 있으므로 출력
    hanoi(n, 1, 2, 3);
}