[풀이]백준 풀이(XV/11729 등)

문제풀이

[RE]하노이의 탑 이동순서(11729, 시뮬레이션)

• 세 개의 장판이 있고 첫 번째 장판에 반경이 서로 다른 n개의 원판이 쌓여있다.
• 쌓인 원판은 크기순으로 쌓여있다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아놓은 원판은 항상 위의 것이 아래의 것 보다 작아야 한다.

위 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하다. (단, 이동 횟수는 최소)

풀이

하노이의 탑 문제는 풀이가 정해져있고 이걸 생각하는 것 보다 찾는게 빠르므로 풀이를 봤다.

• 재귀함수 형태를 사용한다.
• 장판을 A, B, C장판이라고 한다.
• N개의 원반이 있다고 할 때, 작은원반 N-1개를 (A->B)이동.
• 남은 가장 큰 원반을 (A->C) 이동.
• 반복.

n개의 탑을 옮기기 위해서는 등비수열이므로 O(2^N)이 나온다.

잘못된 풀이

stack이나 queue를 쓰겠다고 헛짓을 했다… 문제에서 원하는 정답을 출력하기 어려움

#include <iostream>
#include <stack>
#define END 3
using namespace std;
int n;

stack<int> floor[3];
//(1 to 2) or (2 to 1)에서
void move(int from, int to){
	//3번 바닥에 모든 원판이 이동할 때까지 계속 재귀
	int size = floor[END].size();
	while(size==n){

		//스택이니까 맨 마지막에 넣은걸 먼저 3번으로 얹자!
		floor[END].push(floor[from].top());
		floor[from].pop();
		//옮길게 없거나 사이즈가 꽉차면 끝내고
		if(floor[from].empty() || floor[END].size()==n) return;

		while(!floor[from].empty()){
			floor[to].push(floor[from].top());
			floor[from].pop();
		}
		move(to, from);
	}
	return;
	//마지막 남은 것을 3번으로 옮긴다.
}

int main(){
	cin >> n;
	//a바닥에 1~n까지 집어넣는다.
	for(int i=1; i<=n; i++){
		//a
		floor[0].push(i);
	}
	move(0,1);
}

풀이

위에서 부터 한 칸씩 빼내야 하는 거라 좀 얘기가 다르다.

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<pair<int, int>> v;

void Hanoi(int num, int from, int by, int to)
{
	if (num == 1)
		v.push_back({ from, to });
	else
	{
		Hanoi(num - 1, from, to, by);
		v.push_back({ from, to });
		Hanoi(num - 1, by, from, to);
	}
}
int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;

	Hanoi(N, 1, 2, 3);
	cout << v.size() << "\n";
	for (int i = 0; i < v.size(); i++){
		cout << v[i].first << " " << v[i].second << "\n";
	}
	return 0;
}