[BOJ] C++ 11729 하노이 탑 - 재귀 함수 구조 짜기

11729번: 하노이 탑 이동 순서

예제

3

ans :
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

---

n개의 원판을 기둥 1에서 기둥 3으로 옮기는 문제이다. 이 문제를 평소 풀듯이 생각해보았는데, 감도 안잡혔다. 당장 원판 하나를 어디로 옮겨야 하는지도 모르겠어서 일단 n번째 원판만 생각해보았다.

 

n번 원판을 3번 기둥으로 옮기려면 1 ~ n-1 번 원판이 모두 임시 기둥에 있어야 한다. 그렇다면!! n-1개의 원판을 옮길 수 있다면 n개의 원판을 옮길 수 있다. 이 귀납적 사고를 재귀 함수로 구현해보자.

 

1. 함수 정의

• void func(int n) : n개의 원판을 기둥 1에서 3으로 옮기는 방법을 출력하는 함수
  • 이렇게하면 func(n)에서 func(n-1)을 호출해야하는데 불가능하다. 왜냐하면 n개를 1번에서 3번으로 옮기려면 n-1개를 1번에서 2번으로 옮겨야하기 때문이다. 따라서 함수의 형태가 이렇게 되서는 안된다.
• void func(int a, int b, int n) : n개의 원판을 기둥 a에서 기둥 b로 옮기는 방법 출력
  • 앞의 함수의 단점을 극복하고 별 문제가 없어보인다.

2. base condition

• n = 1일때 그냥 옮기면 되므로 cout << a << ' ' << b << '\n';

3. 재귀식

• n개의 원판을 1에서 3으로 옮겨야한다.
• n-1개의 원판을 출발 기둥과 목표 기둥을 제외한 나머지 임시 기둥으로 옮겨야한다. 
  • 1 + 2 + 3 = 6 이므로 6 - a - b는 나머지 임시 기둥이다.
• 따라서 func(a, 6-a-b, n-1)로 n-1개의 원판을 a에서 임시 기둥으로 옮기고 n번째 원판을 a에서 b로 옮기고 func(6-a-b, b, n-1)로 n-1개의 원판을 다시 b로 옮기면 된다.

이제 원판이 이동한 수를 출력해야하는데, 원판 k개를 옮기기 위해 A번 이동이 필요하다하면 k+1개를 옮길 때는 k개의 원판을 빈 곳으로 옮길 때 A번, K+1번 원판을 옮길 때 1번, k개의 원판을 다시 목적지로 옮길 때 A번이 필요하므로 2A+1번이 필요하다. 이를 바탕으로 n = 1부터 계산하면 이동 횟수가 1, 3, 7, 15가 되므로 총 2^n - 1번 만큼 옮긴다.

/** 재귀 11729 하노이 탑 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

void hanoi(int a, int b, int n)
{
    if (n == 1)
    {
        cout << a << ' ' << b << '\n';
        return;
    }
    hanoi(a, 6 - a - b, n - 1);
    cout << a << ' ' << b << '\n';
    hanoi(6 - a - b, b, n - 1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

이 문제는 평소에 풀듯이 절차지향적으로 사고하면 절대 풀 수 없다. 귀납적 사고로 날먹해보자. 

원판 한 개를 옮길 수 있는 것은 자명하고, n-1개의 원판을 옮길 수 있다고 가정하면 n개의 원판은 당연히 옮길 수 있으므로 날먹하듯이 호로록 코드만 짜면 된다. 

 

 

 

바킹독님의 실전알고리즘을 공부하고 정리한 글입니다.

[실전 알고리즘] 0x0B강 - 재귀