백준(C++) 11729 [하노이 탑 이동 순서]

 

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

접근 방법

하노이 탑은 재귀 함수의 대표적인 문제중 하나이다. 백준 사이트에 가도 여러 개의 하노이 탑 문제를 볼수있다.

그러므로 재귀를 이용할 것이다.

내가 배운 재귀 함수를 만드는 방법은 다음과 같다.

 

1.재귀 함수에는 항상 종료 조건이 있어야한다.

2.재귀는 종료 조건을 만족하지 않는한 자기 자신을 호출해서 재귀를 반복한다.   

 

그래서 이 문제도 이러한 공식으로 접근한다.

 

일단 하노이의 탑 최소 이동거리 공식은  2^n-1번 이다.

이는 C++의 pow를 이용하여 계산하며 된다.

 

다음은 이동 순서 출력이다.

하노이의 탑 이동은 원판을1번째 기둥에서 3번째 기둥으로 하는게 목표이다. 하지만 1번째 기둥에서 3번째로 바로 가는게 아니라 2번째 기둥에 마지막 파츠만 남기고 옮긴후 3번째 기둥으로 옮겨야한다. 

즉,

1번째 기둥에서 3번째 기둥으로 옮기려면

1->2으로 n-1개의 원판을 옮기고, 1->3으로 마지막 원판을 옮기고 2->3으로 n-1개의 원판을 옮기면 끝난다.

 

이를 코드로 만들면

재귀 종료조건은 하노이의탑 최소 이동 순서가 1이 되면 종료.

재귀는 앞서 말한 방법을 작성하면 된다.

내 코드는 다음과 같다.

#include <iostream>
#include <cmath>

using namespace std;

void hanoi(int n, int str, int loc, int det)
{
    if (n == 1)
    {
        cout << str << " " << det << '\n';
    }
    else
    {
        hanoi(n - 1, str, det, loc);
        cout << str << " " << det << '\n';
        hanoi(n - 1, loc, str, det);
    }
}

int main()
{
    cin.tie(0);
    int N;

    cin >> N;
    int k = pow(2, N) - 1;
    cout << k << '\n';
    hanoi(N, 1, 2, 3);
}