스택으로 할 수 있는 처리 중에 제일 대표적인 것이 하노이의 탑 문제입니다. 하노이의 탑은 4개의 블럭으로 쌓여진 탑을 옆에 놓여진 두개의 기둥에 순서를 정해서 옮기면서, 가장 오른쪽 끝에 있는 기둥으로 블럭 크기대로 차곡차곡 쌓는 문제입니다. 최소한도의 옮김으로 해야 합니다. 이때 차곡차곡 쌓아둔 블락을 옮기려면 제일 위에 나중에 쌓은 블럭을 우선 빼내서 옮겨야 하기에, 후입선출(LIFO)로 작동하는 스택에 블럭을 pop하는 구조입니다. 사실 이 설명보다는 재귀호출이라는 원리에 스택이 내부적으로 작동한다고 하는 편이 맞네요. 블럭 후입선출과 스택의 LIFO라기보다 재귀호출의 내부 작동이 파라메터 설정과 해제 등에 스택으로 관여하는 것입니다.
이를 구현하려면 우선 블럭을 옮기는 함수가 필요한데, 블럭을 옮기는 함수는 재귀함수로 정의해서 씁니다. 재귀함수로 하면 코드가 간결해져서 좋습니다. 재귀함수는 자기자신을 호출하는 함수인데, 이 자기자신을 함수에서 실행이 된다는 것은 코딩 부담을 줄여줍니다. 보통 함수는 정의되고나면 호출을 해야 하는데, 직관적으로 볼때 함수 작동이 아직 완료가 안된 라인에서 재귀적으로 자기자신을 자기자신 함수가 호출한다는게 말이 안되게 보이지만, 이러한게 컴파일러에서 제공하는 내적 처리 과정에 의해 제공되는 편의성입니다.
재귀적으로 호출하는 방법의 장단점은 있는데 (1) 데이터가 크면 메모리를 많이 차지함 (2) 처리 속도가 느림 (3) 조건이 부주의하면 끝나지 않게 루프를 돔 (4) 이터레이션이 가능하면 재귀호출을 추천하지 않음 이정도가 단점입니다. 장점은 이터레이션 코드를 줄이고 함수 코드가 시각적으로 간결해집니다.
하노이의 탑으로 돌아오면, 사용자가 입력한 무작위 순서의 A, B, C, D를 입력받아 아래 규칙대로 옮깁니다.
(1) 한번에 하나의 블럭만 옮깁니다.
(2) 맨 위에 있는 블럭만 옮깁니다.
(3) 크기가 작은 블럭 위에는 큰 블럭을 쌓을 수 없습니다.
이 규칙을 지키면서 최소한도의 옮김을 반복해서 제일 오른쪽 기둥으로 옮기면 됩니다.
이 과정을 전체로 다 보이면 이런 순서입니다.
우리가 해야 할 것은 A, B, C ,D를 저장해두고 옮겨지는 과정을 시뮬레이트한 블럭을 옮기는 함수를 정의해서 재귀적으로 호출하는 과정을 표시하는 것입니다. 이 내부적인 재귀 호출 처리에 스택이 쓰이는데 이를 일단 컴파일러의 재량이라고 해두고 소스코드 예시를 해보겠습니다. 그림에서는 4개의 블락인데 그 수를 임의로 입력받아 처리합니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include<stdio.h> void hanoi(int num, char from, char to, char aux) { if (num == 1) { printf("블락 1을 %d 에서 %d 으로 이동\n", from, to); return; } hanoi(num, from, aux, to); printf("블럭 %d 를 %d에서 %d 로 이동", num, from, to); hanoi(num, aux, to, from); return } void main(void) { int num; printf("블락 개수를 입력하세요: "); scanf("%d", &num); hanoi(num, 1, 2, 3); } |