하노이타워(재귀적 구현)

하노이 타워(The Tower of Hanoi)

하노이 타워를 재귀를 이용해 코드로 구현해 볼 것이다. 

하노이 타워의 패턴

우선 원반이 3개인 경우를 설명해 보겠다.(젤 작은 원반이 번호도 작음)

1. 원반1을 A에서 C로 이동

2. 원반2을(를) A에서 B로 이동

3. 원반1을 C에서 B로 이동

4. 원반3을(를) A에서 C로 이동

5. 원반1을 B에서 A로 이동

6. 원반2을(를) B에서 C로 이동

7. 원반1을 A에서 C로 이동

위 과정의 패턴들이 원반의 수가 몇 개가 되든 계속 반복된다. 아래는 원반이 4개인 경우를 그림으로 표현한 것이다.

여기서 원반 1,2,3을 A에서 B로 그리고 B에서 C로 이동시키는 과정이 없는 이유는 앞에서 이미 3개를 다른 막대로 옮기는 과정을 실행했기 때문이다.

따라서 위 내용들을 일반화 시켜보면 다음과 같다.

1. 작은 원반 n-1개를 A에서 B로 이동

2. 큰 원반 1개를 A에서 C로 이동

3. 작은 원반 n-1개를 B에서 C로 이동

Code

#include<stdio.h>
 
void HanoiTowerMove(int num, char from, char by, char to) {
    if (num == 1) {
        printf("원반1을 %c에서 %c로 이동\n", from, to);
    }
    else {
        HanoiTowerMove(num - 1, from, to, by);
        printf("원반%d을(를) %c에서 %c로 이동\n", num, from, to);
        HanoiTowerMove(num - 1, by, from, to);
    }
}
 
int main() {
    HanoiTowerMove(3, 'A', 'B', 'C');
    return 0;
}

재귀를 더 잘 이해하기 위해 하노이 타워를 재귀로 구현했지만 재귀보다는 스택을 사용하는 것이 더 효율적이다.

--------------------------------------------------------------

이 글은 열혈 자료구조를 읽고 정리한 글입니다.