[ 알고리즘 ] 하노이 타워(The Tower of Hanoi) 재귀 함수로 구현하기 (C언어)

C언어로 하노이 타워(The Tower of Hanoi) 재귀 함수로 구현하기 

 

 

하노이 타워 문제는 1883년 프랑스 수학자에 의해 처음 소개되었습니다.

하나의 막대에 쌓여 있는 원반을 다른 막대에 그대로 옮겨야 하는 문제인데, 

막대 3개를 이용할 수 있고, 다음 제약조건을 만족시켜야 합니다. 

 

 

막대 A에서 막대 C로 옮기기 위해서 막대 B를 잘 활용해야 합니다.

직접 연습장에서 어떻게 옮길 것인지 그림으로 그려보고 아래 과정을 확인해보세요. 

 

 

문제 해결 순서 1, 2

문제 해결 순서 3, 4, 5

원반1, 2번을 막대 B에 옮겨다 놓으면 원반 3번을 막대 C에 올길 수 있습니다. 그럼 원반1,2번을 막대 B로 옮겨야 합니다. 이것이 하노이 타워 문제 해결의 핵심입니다. 즉, 모든 원반(3개)를 옮기기전에 우선 두 개의 원반을 막대 B에 옮기는 문제부터 해결해야 합니다. 

 

---

 

만약 원반의 수가 늘어나면 어떻게 처리해야 할까요?

 

 

4번째 원반을 막대 C로 옮기는 것이 우선이니 일단 원반 1,2,3번을 막대 B로 옮겨야 합니다. 

그 다음 원반 4번을  막대 C로 옮깁니다. 그리고 원반 1,2,3번을 막대 C로 옮기면 끝납니다. 

원반 3개를 어떻게 옮기냐구요? 이미 위에서 언급한 방법을 사용하면 됩니다. 

 

 

 

 

---

 

원반 개수 n으로 하고 막대 A에서 막대 C로 옮기는 법을 정리하겠습니다.

 

1. 작은 원반 n-1를 막대 B로 옮긴다.

2 n번째 큰 원반을 막대 C로 옮긴다. 

2. 막대 B에 있던 작은 원반을 막대 C로 옮긴다. 

 

이제 하노이 타워 문제를 재귀 함수 기반으로 해결하겠습니다. 

//num개의 원반을 by이용해서 from에서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to){
    
    if (num == 1) { // 재귀의 탈출 조건: 이동할 원반 수가 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(void) {
	// HanoiTowerMove 함수의 첫번째 인자은 원반의 수를 가리킵니다. 어떤 수가 들어가도 잘 동작합니다. 
    HanoiTowerMove(3, 'A', 'B', 'C');
    return 0;
}

 

 

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

알고리즘 개념 모아보기 

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