하노이의 탑(Tower of Hanoi) 문제란?
유례나 역사 같은 것은 다 생략하고, 문제의 조건 같은 본론부터 바로 말하겠다.
3개의 기둥과 이 기둥에 꽂을 수 있는 다양한 크기에 원판들이 존재한다.
맨 처음 시작할 때, 원판의 크기가 큰 것부터 1번 기둥에 모두 쌓는다.
맨 왼쪽 기둥부터 순서대로 1번, 2번, 3번 기둥이라고 한다.
문제에서 요구하는 것은 아래의 조건을 만족하면서,
1번 기둥에 쌓여있는 모든 원판들을 3번 기둥으로 옮기는 것이다.
조건
1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.
N개의 원판이 최소 경로로 이동할 때의 경로를 출력하라는 것이
문제에서 요구하는 것이다.
이 문제를 왜 알아야 할까?
중요한 것은 학습의 목적이다.
프로그래밍을 배우는 사람들에게는 하노이의 탑을 구현해 보는 것을 추천한다.
왜냐하면 해당 문제가 재귀함수를 가장 잘 설명하고 있는 대표적인 문제이기 때문이다.
프로그래밍 입문자분들이 어려워하시는 부분이 재귀함수이다.
재귀함수는 코딩테스트, 즉 알고리즘을 풀 때
DP(동적계획법), DFS(깊이 우선 탐색), 백트래킹(BackTracking) 기법 등에
사용되기 때문에 필수적으로 알아야 한다.
그리고 하노이의 탑의 로직을 이해하고 코드로 구현할 수 있다면
재귀함수에 대한 감이 잡히고, 더욱 익숙해지실 수 있을 것이다.
그래서 여러분들의 이해를 돕기 위해 그림 자료를 이용하여 최대한 명료하게 설명하려고 노력하겠다.
최소 경로로 시뮬레이션
일단 우리는 1번 기둥에 있는 원판들을 3번 기둥으로 최소 경로로 이동시켜야 한다.
N = 2일 때, 그러니까 원판이 2개일 때부터 생각해 보자.
위 그림과 같은 경로가 N = 2 일 때의 최소 경로가 된다.
최소 이동 횟수는 3번이 된다.
그러면 N = 3 일 때의 경로를 보자
원판이 한 개 늘었을 뿐인데, 최소 이동 횟수가 7번으로 늘었다.
그리고 원판이 어디에서 어디로 이동하는지 순서대로 출력하는 상당히 머리 아프다.
간단하게 생각해 보기
N = 2 일 때는 움직임이 굉장히 간단하다.
그냥 가장 아래 원판 하나와 윗블록 하나, 이렇게 2개밖에 없기 때문이다.
그냥 다른 원판들의 경로도 이렇게 간단하면 편하지 않을까?
그렇게 해서 탄생한 알고리즘이 아래에서 소개할 알고리즘이다.
결국 모든 움직임의 베이스가 되는 것은 N = 2 일 때의 움직임이다.
원판의 개수와 상관없이, N = 2처럼 움직여주기 위해 원판을 2 등분해 준다.
원하는 목표는 가장 큰 것부터 3번 기둥에 차곡차곡 쌓는 것이므로,
가장 아래에 있는 원판 하나와, 그 나머지로 2 등분한다.
이렇게 하면 당연히 편해질 것이다.
그런데 우리는 조건에 의해 원판을 하나씩밖에 움직일 수 없다.
여기서 생각을 해보자.
5개의 원판을 뭉쳐놓은 집합을 하나의 원판으로 봤기 때문에
N = 2의 움직임에 따르면 위의 그림처럼 되어야 한다.
5개를 한 번에 옮길 수 없으므로, 원판을 하나씩 옮겨서 위의 모양을 만들어야 한다.
근데 저 상황 어디서 많이 본 것 같다.
반복되는 상황과 질문
우리가 가장 처음에 구해야 했던 것을 생각해 보자.
일단 위의 상황대로라면 N = 6 일 때, 즉 원판이 6개일 때
1번 기둥에 있던 원판을 모두 6번 원판으로 옮기는 것이다.
그리고 이 상황에서는 5개의 원판을 모두 2번 기둥으로 옮겨야 한다.
다르게 말하면 1번 기둥에 있던 모든 원판을 2번 기둥으로 옮겨야 한다.
이 2개를 비교해서 보자.
둘 다 개수와 위치만 다르지 옮겨야 하는 모양과 조건은 모두 같다.
즉, 동일한 문제가 N과 시작위치와 도착위치만 달라진 채로 반복된다는 소리이다.
한번 계속해보자.
그럼 이렇게 쌓기 위해서는 어떻게 해야 할까?
간단하다. 위에서 했던 것처럼 또 2 등분해 주면 된다.
원래 뭉쳐있던 집합에서도 가장 아랫 원판과 나머지 원판으로 2 등분해 준다.
그리고 이번에는 1번 기둥에서 2번 기둥으로 옮기는 것이기 때문에
3번 기둥으로 집합을 옮겨야 한다.
이러한 과정이 계속 반복된다.
모든 경로 계산하기
위의 설명을 통해서 N개의 원판이 존재한다고 가정했을 때,
맨 아래 원판과 나머지 원판으로 2 등분한다.
이 2등분을 가지고 N = 2의 경로를 흉내 내면
시작위치와 도착위치, 그리고 원판의 개수가
N-1씩 줄어드는 동일한 문제가 반복적으로 호출되는 것을 확인할 수 있다.
위에서 한 것은 1번 과정을 한 것이다.
이제 2번과 3번 과정을 따라가 보자.
사실 2번의 과정은 가장 아래 원판 1개만 남은 것이기 때문에
그냥 도착지로 옮겨주면 끝이다. 그래서 사실 볼 것이 없다.
3번 과정을 보자.
3번에서 옮겨지는 것은 N-1개의 집합이다.
이 집합을 또다시 뭉텅이로 옮기는 것이기 때문에
1번에서 했던 과정을 동일하게 진행해줘야 한다.
달라지는 것은 출발지와 도착지의 기둥 번호뿐이다.
즉 순서는 다음과 같다. N개의 기둥을 옮길 때,
Hanoi(N-1,1,2) : N-1개의 원판을 1번에서 2번 기둥으로 옮김
Hanoi(1,1,3) : 가장 아래의 원판을 1번에서 3번 기둥으로 옮김
Hanoi(N-1,2,3) : 2번 기둥으로 옮겨졌던 N-1개의 원판을 3번 기둥으로 옮겨줌
일반화
N개의 원판 입장에서 보면 이렇다. 하지만 이건 일반화가 아니다.
왜냐하면 위에서 봤듯이 1번에서 2번으로 가는 경우도 있고,
2번에서 3번으로 가는 경우도 있다.
즉 모든 함수에 적용될 수 있도록 해야 한다.
(시작 지점, 도착 지점)이라고 한다면
N-1개의 원판은 시작지점과 도착지점을 제외한 나머지 번호의 기둥으로 간다.
1,2,3번 이므로 이를 식으로 나타내면 6-(시작지점 + 도착지점)을 하면 된다.
나머지는 모두 시작지점, 도착지점을 그대로 넣어주면 된다.
Hanoi(N-1, start,6-(start+end))
Hanoi(1, start, end)
Hanoi(N-1,6-(start+end), end)
최종적으로 일반화된 식은 이렇게 나온다.
하노이의 탑 코드 구현
이제 위의 일반화된 식을 이용해 C++을 이용해서 코드를 작성해 보겠다.
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> ans;
// 하노이의 탑 재귀함수(원판의 개수, 시작, 도착)
void hanoi(int num, int start, int end){
if(num == 1){
vector<int> tmp{start,end};
ans.push_back(tmp);
return;
}
// 위에서 일반화한 식
hanoi(num-1,start,6-(start+end));
hanoi(1,start,end);
hanoi(num-1,6-(start+end),end);
}
int main(){
int input = 4; // N = 4 일때
hanoi(input,1,3);
for(int i = 0; i < ans.size(); i++){
printf("[%d]번째 [%d]번에서 [%d]으로 이동\n",i+1,ans[i][0],ans[i][1]);
}
}
정상적으로 움직임이 포착되는 것을 확인할 수 있다.
이상으로 포스팅을 마치겠다.
재귀함수를 어려워하는 분들이 해당 포스팅을 보고 도움이 됐으면 하는 바람이다.