백준 11729번 : 하노이 탑 이동 순서

⭐️ 하노이 탑의 이동 순서

1. n-1개의 원판을 기둥 1에서 기둥 2로 옮긴다.
2. n번 원판을 기둥 1에서 기둥 3으로 옮긴다.
3. n-1개의 원판을 기둥 2에서 기둥 3으로 옮긴다.

✅ 결론

원판이 n-1 개일 때 옮길 수 있으면 원판이 n개일 때도 옮길 수 있다.

예시 : 원판이 3개일 때

🔎 귀납적 사고

1. 원판이 1개일 때 원판을 내가 원하는 곳으로 옮길 수 있다.
2. 원판이 k개일 때 옮길 수 있으면 k+1개일 때도 옮길 수 있다.

위가 모두 참이면 원판이 n개일 때도 옮길 수 있다.

문제 분석

• 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
• 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
• 원판이 옮겨질 때 원판의 출발지인 탑 번호와 도착지인 탑 번호를 출력한다.
• 원판의 총 이동의 최소 횟수를 출력한다.

구현 절차

1. 함수의 정의 : 함수가 어떤 역할을 수행하고, 어떤 인자를 받는지 결정한다.

void func(int a, int b, int n) // 기둥 a에서 기둥 b로 n개의 원판을 옮기는 역할

2. base condition 설정 : n=1일 때 기둥 a에서 기둥 b로 원판을 옮긴다.

if(n == 1) cout << a << ' ' << b << "\n" // 기둥 a에 남아있는 마지막 1개의 원판을 기둥 b로 옮긴다.

3. 재귀 식 : 기둥들의 번호의 합이 6이기 때문에 기둥들의 번호는 각각 a, 6-a-b, b이다.

func(a, 6-a-b, n-1) // n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다.
cout << a << ' ' << b << '\n' // n번 원판을 기둥 a에서 기둥 b로 옮긴다.
func(6-a-b, b, n-1) // n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다.

코드

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

// 기둥 a에서 기둥 b로 n개의 원판 이동
void hanoi(int a, int b, int n) {

    // 기둥 a에 남아있는 원판이 1개일 경우 기둥 b로 옮기고 종료
    if (n == 1) {
        cout << a << ' ' << b << "\n";
        return;
    }

    // 1. 기둥 a에 있는 n-1개의 원판을 보조 기둥(6 - a - b)으로 이동
    hanoi(a, 6 - a - b, n - 1);

    // 2. 가장 큰 n번째 원판을 기둥 a에서 기둥 b로 이동
    cout << a << ' ' << b << "\n";

    // 3. 보조 기둥에 있던 n-1개의 원판을 기둥 b로 이동
    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);

}

✅ 비트 연산자

int a = 3;        // 0000 0011
int b = a << 1;   // 0000 0110  -> b는 6 (3 * 2^1)

int c = 12;        // 0000 1100
int d = c >> 1;   // 0000 0110  -> d는 6 (12 / 2^1)

• << : 비트를 왼쪽으로 이동시키는 연산자, 2의 n제곱만큼 곱하기와 같다.
• >> : 비트를 오른쪽으로 이동시키는 연산자, 2의 n제곱만큼 나누기와 같다.

✅ 원판의 최소 이동 횟수

• 원판 k개를 옮길 경우 : 총 a번 이동해야 한다.
• 원판 k+1개를 옮길 경우 : k개의 원판을 중간 기둥으로 옮길 때, a번 + k+1번째 원판을 최종 기둥으로 옮길 때, 1번 + k개의 원판을 최종 기둥으로 옮길 때, a번 = 총 2*a + 1 번 이동해야 한다.

k가 1일 때 최소 이동 횟수는 1번 , 즉 초항이 1이므로 최소 이동 횟수의 일반항은 2^k - 1 가 된다.