BOJ 11729 - 하노이 탑 이동

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

3개의 장대가 있고 크기가 다른 원판이 장대에 쌓여있다.

1번의 장대에 쌓여있는 원판을 3번의 장대로 이동하는데 걸리는 최소횟수와 과정을 출력하시오.

• 조건

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

Solution

너무나도 유명한 하노이탑 문제이다.

재귀적으로 해결할 수 있는데

만약 n개의 원판이 존재한다면 n번 원판을 3번으로 옮기기 위해서는

(1) n-1개의 원판을 2번으로 옮긴다.
(2) n번 원판을 3번으로 옮긴다.
(3) n-1개의 원판을 3번으로 옮긴다.

와 같이 정의 할 수 있다.

위와 같이 일반화했을때 그 안의 작은 문제들은 알아서 풀리게 된다.

또한 이동횟수는 일반항을 구할수 있는데

결론만 말하자면 2^n - 1 번이다. 이 부분은 검색해서 확인해보는것을 추천!

Code

#include <bits/stdc++.h>
using namespace std;

void hanoi(int n, int from, int by, int to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, by);
    //cout << n << "번 원판을 " << from << " 에서 " << to << " 로 옮긴다 \n";
   cout << from << ' ' << to << '\n';
    hanoi(n - 1, by, from, to);

    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    long long ans = 1;
    cin >> n;
    for (int i = 0; i < n; i++)
        ans *= 2;
    cout << ans - 1 << '\n';
    hanoi(n, 1, 2, 3);

    return 0;
}

자료구조를 공부할때 열혈 자료구조로 공부하였었는데 초반에 재귀관련하여 하노이 탑 설명이 있었다. 당시에 아주 신기하게 느꼈었던 기억이 ..

위 문제는 by 변수를 사용하지않고 출발점과 도착점으로만으로도 코드를 만들수 있다.

#include <bits/stdc++.h>
using namespace std;

void hanoi(int n, int from, int to) {
    if (n == 0) return;
    hanoi(n - 1, from, 6 - from - to);
   cout << from << ' ' << to << '\n';
    hanoi(n - 1, 6-from-to,to);

    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    long long ans = 1;
    cin >> n;
    for (int i = 0; i < n; i++)
        ans *= 2;
    cout << ans - 1 << '\n';
    hanoi(n, 1, 3);

    return 0;
}

++ 처음에는 pow함수로 이동횟수를 출력했는데 float형으로 반환되기에 위와같이 단순히 반복문을 이용하였다.

참고 : 윤성우의 열혈 자료구조 , https://code.plus/course/43 , 분할 정복(연습)