[백준 11729] 하노이 탑 이동 순서

🔗문제 풀러가기
단계별로 풀어보기 단계 21의 7번째 문제이다.

문제 분석

재귀함수를 이용하여 문제를 해결하였다.

재귀함수에 대해 정리한 글

코드

#include <iostream>
using namespace std;

void Hanoi(int n, int from, int to, int sec)
{
    if (n == 1)
    {
        cout << from << " " << to << "\n";
        return;
    }

    Hanoi(n - 1, from, sec, to);
    cout << from << " " << to << "\n";
    Hanoi(n - 1, sec, to, from);
}

int main()
{
    int n;
    cin >> n;

    cout << (1 << n) - 1 << "\n";

    Hanoi(n, 1, 3, 2);
}

해석

1. n을 입력받은 후 옮긴 횟수를 출력한다.

2. 그 후 Hanoi 함수를 실행한다.
   Hanoi 함수에서 매개변수들은 다음과 같은 역할을 한다.

   n: 원판의 개수
   from: 옮기기 전 탑
   to: 옮길 탑
   sec: 나머지 탑

3. 만약 현재 원판의 개수가 1이라면 from과 to를 출력한다.
   그후 return을 통해 재귀를 종료한다.

4. 그렇지 않다면, n-1개의 원판을 from에서 sec로 옮긴다.

5. 원판을 옮겼으므로 from과 to를 출력한다.

6. 그 후, sec에서 to로 옮기면 끝!