하노이탑 이동 순서 (boj.kr/11729)

하노이탑 이동 순서 (boj.kr/11729)

 

문제 해설 및 주의사항

- 하노이 탑의 최소 이동 순서를 출력하는 프로그램을 작성하자.

- 첫 번째 장대에 쌓인 원판의 개수 N 이 주어진다.

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 규칙을 찾아보자.

- m 개의 원판을 3번째 장대로 옮긴다고 해보자. 그렇다면,

 

1. 먼저 위의 m - 1개의 원판을 2번째 장대로 옮기고 ( a_(m-1) )

2. 남은 1개의 원판을 3번째 장대로 옮기고 ( + 1)

3. 2번째 장대의 m - 1 개 원판을 3번째 장대로 옮긴다. ( a_(m-1) )

 

최단 이동 횟수의 점화식은

a_n = 2a_(n - 1) + 1

이 될 것이다.

 

2. 함수의 구현

- 재귀를 호출 할 때 달라지는 것은 무엇일까

 

a. 목적지 장대 ( 1, 2, 3 중 하나 ) (end)

b. 출발지 장대 ( start)

b. 원판의 갯수 (num)

 

풀이코드

#include <iostream>
#include <algorithm>
using namespace std;
// 1780 종이의 개수
 
vector<pair<int, int>> ans;
 
int solve(int num, int start, int end){
	if(num == 1){
		ans.push_back(make_pair(start, end));
		return 1;
	}
 
	int ret = 0;
	
	// 1. 먼저 위의 m - 1개의 원판을 2번째 장대로 옮기고 ( a_(m-1) )
	ret += solve(num - 1, start, 6 - (start + end));
	
	// 2. 남은 1개의 원판을 3번째 장대로 옮기고 ( + 1)
	ret += solve(1, start, end);
	
	//3. 2번째 장대의 m - 1 개 원판을 3번째 장대로 옮긴다. ( a_(m-1) )
	ret += solve(num - 1, 6 - (start + end), end);
	
	return ret;
}
 
int main(){
	int n;
	cin >> n;
	
	cout << solve(n, 1, 3) << endl;
	
	for(pair<int,int> p : ans){
		printf("%d %d\n",p.first, p.second);
	}
}

 

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 출력 형식의 잘못

- 처음 제출할 때, 이동 순서를 먼저 출력하였다. 최소 이동 횟수 출력 후 이동 순서를 출력해야 한다는 점을 유의했어야 했다.

2. 분할 정복이란?

- 결국 문제를 어떻게 분할 하는 것이냐가 관건이다. 그렇게 하기 위해서는 함수를 구현할 때, 파라미터로 무엇을 넣어야 하는지 부터 잘 생각해보아야 하며, 코드 짜는 것에 돌입하기 전에 문제를 분할하는 과정들을 세세히 말해두어야 한다. 

 

위의 글에서 나눈 것처럼 재귀함수에서도 똑같이 분할하였더니 답이 나왔다.