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

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11729번 문제인 하노이 탑 이동 순서이다.
문제는 아래 링크를 확인하자.

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

11729번: 하노이 탑 이동 순서

하노이 탑 문제는 잘 알려진 유명한 문제이므로 문제에 대한 설명은 생략한다.

 

탑 A를 B로 옮기려면, A의 바닥을 제외한 나머지를 제 3의 바닥 C로 옮기고 A의 바닥을 B로 옮긴 다음, C에 옮겨둔 탑을 다시 B로 옮기면 된다.

 

이 과정은 재귀적으로 구현이 가능하다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

void hanoi(int N, int A, int B, int C) { // A: 시작위치 B: 도착위치 C: (상대적) 빈칸
	if (N == 1) cout << A << ' ' << B << '\n';
	else {
		hanoi(N - 1, A, C, B);
		cout << A << ' ' << B << '\n';
		hanoi(N - 1, C, B, A);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int idx = 1;
	int N; cin >> N;
	for (int i = 1; i < N; i++) {
		idx <<= 1; idx++;
	}
	cout << idx << '\n';
	hanoi(N, 1, 3, 2);
}