[BOJ-11729][C++] 하노이 탑 이동 순서

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

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

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

 

 

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

예제 입력 1 

3

 

예제 출력 1 

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

 

 

알고리즘 분류

• 재귀

 

문제 출처

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

11729번: 하노이 탑 이동 순서

 

---

 

문제 해결 방법

• 하노이 탑 알고리즘을 이용하여 문제를 해결하였다.
  • 하노이 탑 알고리즘에서 `N` 개의 원판을 옮기는 최소의 수는 $2^{N} - 1$ 이다.
• `N` 개의 원판을 옮기는 최소의 수를 출력하려고 할 때, 다음과 같이 pow() 함수를 사용하였다.

// 하노이 탑에서 원판을 옮기는 최소 횟수 : 2^n - 1
cout << (int)(pow(2, N)) - 1 << '\n';

• pow() 함수는 double 형을 활용하여 작동되기 때문에 `N`의 최댓값인 20이 입력되면 오차 범위가 커져 틀리게 된다고 한다.
• 따라서 pow() 함수를 이용하여 계산한 후, int 형으로 명시적으로 변환해주었다.
• $2^{N}$ 의 값을 구하기 위해 다음과 같이 왼쪽 시프트 연산자(<<)를 사용할 수도 있다고 한다.

// 하노이 탑에서 원판을 옮기는 최소 횟수 : 2^n - 1
cout << (1 << N) - 1 << '\n';

 

코드

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

int N;

void hanoi_tower(int n, int from, int tmp, int to) {
    if (n == 1) {
        cout << from << " " << to << '\n';
    }
    else {
        hanoi_tower(n - 1, from, to, tmp);
        cout << from << " " << to << '\n';
        hanoi_tower(n - 1, tmp, from, to);
    }
}

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

    cin >> N;

    // 하노이 탑에서 원판을 옮기는 최소 횟수 : 2^n - 1
    cout << (int)(pow(2, N)) - 1 << '\n';   // 또는 (1 << N) - 1, pow()를 사용할 때 int 형으로 명시적으로 변환해준다.
    
    hanoi_tower(N, 1, 2, 3);

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [재귀]
• 실버I

 

하노이 탑(Tower of Hanoi)

개념

• 프랑스의 수학자 에두아르 뤼카(François Édouard Anatole Lucas)가 1883년 소개한 유명한 문제
• 재귀(Recursion)를 연습하는데 도움이 되는 알고리즘
• 다음과 같이 3개의 막대와 N개의 원판(Disk)이 있을 때, 원판을 다음의 순서를 지키면서 A에서 C로 옮기는 작업
  • 각 원판의 크기는 모두 다르다.
  • 원판의 크기는 아래에서부터 위로 갈수로 점점 작아진다.

원판이 3개일 때 하노이 탑 알고리즘 과정

① 한 번에 하나의 원판만 이동한다.
② 맨 위에 있는 원판만 이동한다.
③ 크기가 작은 원판 위에 큰 원판을 쌓을 수 없다.

 

• 이 조건에서 다음을 구하는 것이 하노이 탑의 문제가 된다.

① 최소의 이동 횟수로 옮기는 가짓수 ($2^{N} - 1$)
② 최소의 이동 횟수로 옮길 때, 각 원반을 옮기는 순서

 

알고리즘

void hanoi(int N, char from, char tmp, char to) {
    if (N == 1) {
        cout << N << "번 원반을 " << from << "에서 " << to << "로 이동" << '\n';
    }
    else {
       hanoi(N - 1, from, to, tmp);
       cout << N << "번 원반을 " << from << "에서 " << to << "로 이동" << '\n';
       hanoi(N - 1, tmp, from, to);
   }
}

 

사용 예

#include <iostream>
using namespace std;

void hanoi(int N, char from, char tmp, char to) {
    if (N == 1) {
        cout << N << "번 원반을 " << from << "에서 " << to << "로 이동" << '\n';
    }
    else {
       hanoi(N - 1, from, to, tmp);
       cout << N << "번 원반을 " << from << "에서 " << to << "로 이동" << '\n';
       hanoi(N - 1, tmp, from, to);
   }
}

int main() {
    hanoi(3, 'A', 'B', 'C');
    
    return 0;
}

1번 원반을 A에서 C로 이동
2번 원반을 A에서 B로 이동
1번 원반을 C에서 B로 이동
3번 원반을 A에서 C로 이동
1번 원반을 B에서 A로 이동
2번 원반을 B에서 C로 이동
1번 원반을 A에서 C로 이동

 

참고 사이트

• https://shoark7.github.io/programming/algorithm/tower-of-hanoi