재귀함수의 기본 알고리즘으로 유명한 하노이의 탑 알고리즘이다.
하노이의 탑은 3개의 기둥을 옮겨가며 원판을 마지막 기둥으로 모두 옮기는 게임이다.
이 때, 그냥 원판을 옮기는 것이 아닌 아래와 같은 조건이 붙는다.
- 자신의 크기보다 큰 원판은 위에 얹을 수 없다.
- 한 번에 움직일 수 있는 원판은 하나이다.
이런 조건 하에, 최소 이동횟수로 옮기는 가짓 수를 구하거나
최소 이동횟수로 옮기는 과정을 적는 문제가 보통 하노이의 탑 문제이다.
그럼 이 문제를 어떻게 코드로 구현을 할 것인가? 체계적으로 접근을 해보자.
규칙 찾기
우리가 특정 문제를 함수화 시킬 때에는 규칙을 찾는 것이 중요하다.
그렇지 않으면 깔끔하지 않은 중구난방 코드가 되어 버린다.
과연 하노이의 탑의 이동 경로에는 어떤 규칙이 있을까??
[사진 첨부]
위의 그림을 보며 곰곰히 생각을 해보자.
과연 가장 아래에 있는 제일 큰 원판을 옮기려면 어떻게 옮겨야 하는가?
제일 큰 원판의 번호를 N이라고 가정해보자.
그럼 위 그림과 같이 N-1 까지의 원판들을 중간 기둥으로 옮겨야만 한다.
이후 2번 원판을 3번 원판 위로 올리고 싶을 때도 마찬가지다.
1번 원판을 남은 기둥으로 옮긴 뒤, 목적지인 3번 원판으로 옮긴다.
정리해보면 다음과 같은 과정을 계속 반복하는 것이다.
- N-1개의 원판을 1번 막대에서 2번 막대로 옮긴다.
- 남은 N번 원판을 3번 막대로 옮긴다.
- 다시 N-1개의 원판을 2번 막대에서 3번 막대로 옮긴다.
위 3가지 과정을 N == 1 일 때까지 반복하면? 하노이의 탑 문제는 풀릴 것이다.
즉 이 문제는, 재귀를 이용
함수 구현
위에서 생각했던 3가지 과정을 이제 그대로 함수식으로 옮겨보자.
- N-1개의 원판을 1번 막대에서 2번 막대로 옮긴다.
- function(N-1, 1, 2, 3)
- N-1개의 원판을 1번 기둥에서 3번을 거쳐 2번 기둥으로 옮긴다.
- N번 원판을 3번 기둥으로 옮긴다.
- 다시 N-1개의 원판을 2번 막대에서 3번 막대로 옮긴다.
- function(N-1, 2, 3, 1)
- N-1개의 원판을 2번 기둥에서 1번을 거쳐 3번 기둥으로 옮긴다.
위의 함수 식들을 재귀하며, N == 1이 되는 순간, 1번 원판을 3번 기둥으로 옮기고 종료한다.
실제 코드
#include <string>
#include <vector>
using namespace std;
void do_hanoi(int n, int from, int via, int to, vector<vector<int>>& answer) {
if (n == 1)
answer.push_back({ from, to });
else {
do_hanoi(n - 1, from, to, via, answer);
answer.push_back({ from, to });
do_hanoi(n - 1, via, from, to, answer);
}
}
vector<vector<int>> solution(int n) {
vector<vector<int>> answer;
do_hanoi(n, 1, 2, 3, answer);
return answer;
}