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

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

하노이의 탑은 재귀적인 방법으로 간단하게 구현할 수 있다.

현재 원판의 위치를 from, 원판을 이동시킬 위치를 to, 나머지 기둥을 tmp, 원판의 크기를 n이라고 하자.

 

1. 현재 옮기고자 하는 크기 n인 원판 위에 있는 크기 n-1인 원판을 tmp로 옮긴다. 이 때, 크기 n-1인 원판의 목적지(to)는 tmp위치가 되므로 to와 tmp를 스왑하여 매개변수로 넘겨준다.

2. 크기 n인 원판을 목적지인 to로 옮긴다. 이 때 실질적으로 이동이 일어나므로 log_data에 넣어준다.

3. 크기 n-1인 원판을 다시 크기 n인 고리 위로 올린다. 이 때, 크기 n-1인 원판의 출발지(from)는 tmp이므로 from과 tmp를 스왑하여 매개변수로 넘겨준다.

 

위의 로직으로 재귀호출해주면 하노이의 탑의 이동 순서를 알 수 있다.

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

vector<pair<int, int>> log_data;

//재귀 풀이
void hanoi(int n, int from, int tmp, int to) {
	if (n == 1) {
		log_data.emplace_back(from, to);
		return;
	}
	hanoi(n - 1, from, to, tmp);
	log_data.emplace_back(from, to);
	hanoi(n - 1, tmp, from, to);
}

//비재귀 풀이
vector<tuple<int,int,int,int>> stack;
void hanoi_with_non_recursion(int n, int from, int tmp, int to) {
	int tmp_swap;
	while (1) {
		while (n > 1) {
			stack.emplace_back(n, from, tmp, to);
			tmp_swap = tmp;
			tmp = to;
			to = tmp_swap;
			n--;
		}
		// n = 1인 원판 from -> to
		log_data.emplace_back(from, to);
		if (stack.size() == 0) break;

		tie(n, from, tmp, to) = stack.back();
		stack.pop_back();
		
		log_data.emplace_back(from, to);
		tmp_swap = tmp;
		tmp = from;
		from = tmp_swap;
		n--;
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
    
	hanoi(n, 1, 2, 3);
    
	cout << log_data.size() << '\n';
	for (auto& i : log_data) cout << i.first << ' ' << i.second << '\n';
	return 0;
}

메모리: 14432 kb

시간: 136 ms

아래는 비재귀적으로 짠 코드인데 백준에 제출 했을 때는 메모리와 시간이 재귀방법과 동일하게 나왔고, 직접 실행 시간을 체크해 봤을 때는 n = 20일 때 기준으로 비재귀코드가 재귀코드보다 실행 시간이 두배나 더 길었다. 튜플로 묶고 풀고 하는 연산이 추가되어서 그런 것일까? 잘 모르겠다. 어쨋든 조금 찝찝하긴 하지만 비재귀적 방법이 항상 재귀적 방법보다 효율적인 것은 아니라는 점을 배웠다.

 

아래는 재귀함수를 비재귀함수로 바꾸는 공식...! 신기해서 들고왔다.

wiki.gurubee.net/pages/viewpage.action?pageId=1507916

4.2 재귀 함수를 비재귀 함수로 바꾸기 - [종료]구루비 Dev 스터디 - 개발자, DBA가 함께 만들어가는