백준 11729 c++ "하노이 탑 이동 순서" -PlusUltraCode-

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

[필자 사고]

하노이 탑은 전형적인 재귀 관련된 문제다.

일종의 일화가 있는데 재귀를 이용하지 않을 경우 너무나 많은 시간이 소요되는 문제로 유명하다.

재귀를 이용하게 되면 엄청 짧은 시간 안에 해당 문제를 타파할 수 있게된다. 

 

아래는 자세한 코드해설이다.

[코드 해설]

프로그램의 목적

이 코드는 하노이 탑 문제를 해결하는 프로그램입니다.
입력으로 원판의 개수 NNN을 받고,

1. 원판을 모두 옮기는 데 필요한 최소 이동 횟수를 계산해 출력합니다.
2. 실제로 어떤 순서로 원판을 옮겨야 하는지를 한 줄씩 출력합니다.

---

전체 흐름

1. main 함수에서 원판 개수 NNN을 입력받습니다.
2. 최소 이동 횟수 2N−12^N - 12N−1을 계산해 출력합니다.
3. 하노이 탑 재귀 함수인 hanoi를 호출하여 이동 과정을 출력합니다.

---

최소 이동 횟수 계산

• 하노이 탑에서 원판이 NNN개일 때 필요한 최소 이동 횟수는 항상 2N−12^N - 12N−1입니다.
• 코드에서는 비트 연산을 활용해 1 << N으로 2N2^N2N을 계산한 뒤, 1을 빼서 2N−12^N - 12N−1을 얻습니다.

---

hanoi 함수의 역할

hanoi(num, start, to, bypass)는

• num: 옮겨야 할 원판의 수
• start: 출발 기둥
• to: 목표 기둥
• bypass: 보조 기둥
  을 의미합니다.

함수는 다음 규칙으로 동작합니다.

1. 원판이 하나만 있을 때
   • 바로 출발 기둥에서 목표 기둥으로 옮기면 됩니다.
   • 이 경우 단 한 줄의 이동만 출력합니다.
2. 원판이 두 개 이상일 때
   • 가장 큰 원판을 옮기기 위해 위에 있는 작은 원판들을 보조 기둥으로 옮겨야 합니다.
   • 따라서 다음 순서로 진행됩니다.
     1. num-1개의 원판을 보조 기둥으로 옮깁니다.
     2. 가장 큰 원판 하나를 출발 기둥에서 목표 기둥으로 옮깁니다.
     3. 보조 기둥에 있던 num-1개의 원판을 다시 목표 기둥으로 옮깁니다.

---

예시: 원판이 3개일 때

• 처음에는 1번 기둥에서 3번 기둥으로 모두 옮기려 합니다.
• 먼저 위의 2개 원판을 2번 기둥으로 옮깁니다.
• 그다음 가장 큰 원판을 1번 기둥에서 3번 기둥으로 옮깁니다.
• 마지막으로 2번 기둥에 있던 2개 원판을 3번 기둥으로 옮깁니다.

결국 이 과정을 통해 최소 7번의 이동으로 모든 원판을 옮길 수 있고, 함수는 그 과정을 차례대로 출력합니다.

[소스 코드]

#include <iostream>
using namespace std;
void hanoi(int num, int start, int to, int bypass) {
	if (num == 1) {
		cout << start << " " << to << "\n";
		return;
	}
	else {
		hanoi(num - 1, start, bypass, to);
		cout << start << " " << to << "\n";
		hanoi(num - 1, bypass, to, start);
	}
}

int main(void) {
	int N;
	cin >> N;
	cout << (1 << N) - 1 << "\n";
	hanoi(N, 1, 3, 2);
}