하노이의 탑
하노이의 탑(Towers of Hanoi)은 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제입니다. 모든 원반은 크기가 다르고 처음에는 모든 원반이 규칙에 맞게 첫 번쨰 기둥에 쌓여 있습니다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 됩니다. 최소의 횟수로 옮겨야 하며, 원반은 한개씩 옮길수 있고 작은 원반위에 큰 원반이 있으면 안됩니다.
시작 기둥 : 처음 원반이 놓인 기둥
목표 기둥 : 이동할 목적지의 기둥
중간 기둥 : 남은 중간의 기둥
A는 1과 2번은 원반이 하나의 그룹으로 이동하는 과정입니다.
B는 1이 하나의 그룹으로 이동하는 과정입니다.
위의 두 과정을 보면 하노의 탑은 일련의 과정을 거칩니다.
- 하노이의 탑은 아래의 3과정을 거칩니다.
- 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no - 1])을 시작 기둥에서 중간 기둥으로 옯깁니다.
- 바닥 원반 no를 시작 기둥에서 목표기둥으로 옮겼음을 출력합니다.
- 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no ~ 1])을 중간 기둥에서 목표 기둥으로 옮깁니다.
이렇게 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법을 divide and conquer(분할 해결법)이라고 합니다.
하노이의 탑을 구현하는 프로그램을 살펴봅시다.
원반의 개수는 no, 시작 기둥 번호는 x, 목표 기둥 번호는 y입니다.
하노이의 탑 알고리즘의 구현 3과정을 코드로 작성된한 것 뿐입니다.
#include <stdio.h>
/* 원반[1] ~ 원반[no]를 x기둥에서 y기둥으로 옮김*/
void move(int no, int x, int y) {
if (no > 1) // 베이스 케이스(중단 조건)
move(no - 1, x, 6 - x - y); // 그룹을 시작기둥에서 중간기둥으로 옮김
printf("원반[%d]를 %d 기둥에서 %d 기둥으로 옮김\n", no, x, y); // 바닥 원반 no를 시작 기둥에서 목표기둥으로 옮겼음을 출력
if (no > 1) // 베이스 케이스(중단 조건)
move(no - 1, 6 - x - y, y); // 그룹을 중간기둥에서 목표기둥으로 옮김
}
int main(void)
{
int n;
printf("하노이의 탑\n원반 개수 : ");
scanf("%d", &n);
move(n, 1, 3);
return 0;
}
move함수의 매개변수로는 남은원반개수와 x 기둥에서 y 기둥으로 이동할 변수두개로 구현하였습니다.
중단 조건은 원반개수가 0이 되었을때 이고 매번 원반 번호과 몇번째 기둥에서 몇번째 기둥으로 이동했는지가 출력됩니다.
코드를 보면 중간 기둥을 6 - x - y로 표현했습니다. 기둥 번호는 1, 2, 3이 있고 기둥 번호의 합은 6 이므로 시작기둥과 목표 기둥 외의 남은 기둥을 표현하는 것은 6 - x - y입니다. 그렇게 구현하면 어떤 기둥에서 시작하거나 목표 기둥의 구별없이 결과가 잘나옵니다.
