BOJ-1914 | 하노이 탑 c++

✏️ 1914 - 하노이 탑
🌊 GitHub @xaesu, Study-Algorithm

접근

✔️ 재귀함수

1. 하노이의 탑 과정
   → 장대를 from, aux, to라고 할 때,
   → 가장 큰 원판은 항상 from -> to 로 옮긴다.
   → 가장 큰 원판을 제외한 나머지 원판들은 순서대로 aux 장대에 도착한다.
   → aux에 모인 원판들을 대상으로 해당 과정을 다시 반복한다.
   → 재귀의 끝은 가장 작은 원판을 from -> to 로 이동하는 것

2. 하노이의 탑을 옮기는 최소 횟수는 2^n - 1 이다.
   → 지수 값을 구하는 pow() 함수를 사용한다.
   → pow() 함수 : <cmath> 헤더파일 사용 필요

3. 해당 문제에서는 원판의 개수로 입력받을 수 있는 값이 커 이동 횟수를 int로 표현 불가능
   → int보다 더 큰 범위의 정수를 표현할 수 있는 longlong 타입도 표현 불가능했음
   → to_string() : 실수 값을 문자열로 변환하여 출력 (pow의 반환형은 실수)
   → substr() : 문자열 자르기 (Find() 로 소수점을 찾아 정수 부분만 자르기)
   → size() : 문자열 길이 파악 (문자열에서는 length() 와 같은 역할)

풀이

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

string HanoiCount(int n);
void HanoiProcess(int n, int from, int aux, int to);

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

    cout << HanoiCount(N) << '\n';

    // N이 20보다 같거나 작을 때만 과정 출력
    if (N <= 20)
        HanoiProcess(N, 1 , 2, 3);
}

// 하노이 이동 횟수 (2^n - 1)
string HanoiCount(int n) {
    string Hanoi;
    Hanoi = to_string(pow(2, n));
    Hanoi = Hanoi.substr(0, Hanoi.find('.'));
    Hanoi[Hanoi.size() - 1] -= 1;

    return Hanoi;
}

// 하노이 이동 과정
void HanoiProcess(int n, int from, int aux, int to) {
    if (n == 1){
        cout << from << ' ' << to << '\n';
        return;
    }

    // 가장 작은 원판부터 옮기기
    HanoiProcess(n-1, from, to, aux);
    
    // 가장 큰 원판을 From에서 To로 이동
    cout << from << ' ' << to << '\n';

    // 가장 큰 원판을 제외한 나머지 원판에서 순서대로 Mid원판에 있는 상태
    // Mid 장대와 From 장대 순서가 바뀐 상태에서 다시 HanoiProcess 실행
    HanoiProcess(n-1, aux, from, to);
}