11729번 하노이 탑 이동순서

문제 링크 : www.acmicpc.net/problem/11729

 

하노이 탑의 기본 규칙 

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

예를 들어 원반이 3개와 막대 3개가 존재할 때, 알고리즘은

   1,2번 원반 2개를 A->B로 이동. 이때 C 경유 가능

      (1번 원반을 A->C로 이동. 

      2번 원반을 A->B로 이동.

      1번 원반을 C->B로 이동.)

   3번 원반을 A->C로 이동. 

   1,2번 원반 2개를 B->C로 이동. 이때 A 경유 가능 

      (1번 원반을 B->A로 이동.

      2번 원반을 B->C로 이동.

      1번 원반을 A->C로 이동.)

이다. 이를 코드로 바꿔보면 아래와 같다.

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


vector<pair<int, int>> list;
void move(char from, char to) {
	int start = 0;
	int finish = 0;

	if (from == 'A') start = 1;
	else if (from == 'B') start = 2;
	else if (from == 'C') start = 3;
	if (to == 'A') finish = 1;
	else if (to == 'B') finish = 2;
	else if (to == 'C') finish = 3;
	
	list.push_back(make_pair(start, finish));
}
void hanoi(int now, char start, char via, char finish) {
	if (now == 1) {
		move(start, finish);
		return;
	}
	else {
		hanoi(now - 1, start, finish, via);	// 이동해야하는 n원반위 n-1개의 원반을 경유지로 이동
		move(start, finish);				// n 원반을 종착지로 이동
		hanoi(now - 1, via, start, finish);	// via에 있는 n-1개의 원반을 종착지로 이동
	}
}
int main() {
	int N = 0;
	cin >> N;
	
	hanoi(N, 'A', 'B', 'C');

	cout << list.size() << "\n";
	for (unsigned int i = 0; i < list.size(); i++) {
		cout << list[i].first << " " << list[i].second << "\n";
	}
}

 

아래 코드는 위의 코드를 좀 더 간략화시킨 것이다.

 1. 전역 변수를 없애고 하노이탑의 이동 횟수 출력 => 소요시간 감소

 2. 막대를 char 대신 int로 지정함으로서 변환 과정(char->int) 생략

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

void move(int from, int to) {
	cout << from << " " << to << "\n";
}
void hanoi(int now, int start, int via, int finish) {
	if (now == 1) {
		move(start, finish);
		return;
	}
	else {
		hanoi(now - 1, start, finish, via);	// 이동해야하는 n원반위 n-1개의 원반을 경유지로 이동
		move(start, finish);				// n 원반을 종착지로 이동
		hanoi(now - 1, via, start, finish);	// via에 있는 n-1개의 원반을 종착지로 이동
	}
}
int main() {
	int N = 0;
	cin >> N;

	
	cout << (long long int) pow(2, N) - 1 << "\n";
	hanoi(N, 1, 2, 3);
}