3. 하노이탑

하노이탑이란

A의 원판을 하나만 이동하여 모두 C로 이동하는 것이다.

무조건 아래에 위치하는 원판은 위에 위치하는 원판보다 커야하며 작으면 안된다.

 

원판의 개수를 입력받고, 이를 모두 A에서 C로 옮기는 알고리즘을 작성하며

A에서 C로 옮기는 동작을 모두 출력하고

이동횟수를 출력해라.

 

하노이의 탑 - 나무위키 (namu.wiki)

하노이의 탑 - 나무위키

위키에 따르면 정답은 2^n -1 이다. 

자신의 정답과 맞는지 비교해라.

 

필요에 따라 재귀함수를 사용할 수 있다.

책에 의하면 재귀함수를 이용하지 않으면 구할 수 없다고 한다.

 

---

알고리즘 분석

---

원반이 1개 일 때 생각해보자

A의 1원판을 C로 옮긴다.

 

원판이 2개일 때 생각을 해보자

A의 1번원판을 B로 옮기고

A의 2번 원판을 C로 옮기고

B의 1번 원판으 C로 옮긴다.

 

원판이 3개일 때 생각해보자.

A의 1원판을  C로 옮기고

A의 2원판을 B로 옮기고

B의 1원판을 B로 옮기고

A의 3원판을 C로 옮기고

B의 1원판을 A로 옮기고

B의 2원판을 C로 옮기고

A의 1원판을 C로 옮긴다.

 

 규칙을 찾을 수 있을까?

신기하게 하나의 규칙이 보인다. 다시 한 번 보자

원판이 2개 일 때

A의 1번원판을 B로 옮기고

A의 2번 원판을 C로 옮기고

B의 1번 원판을 C로 옮긴다.

 

원판이 3개 일 때

A의 1원판을  C로 옮기고

A의 2원판을 B로 옮기고

C의 1원판을 B로 옮기고

A의 3원판을 C로 옮기고  // 원판이 1개 일 때

B의 1원판을 A로 옮기고

B의 2원판을 C로 옮기고

A의 1원판을 C로 옮긴다.

 

원판이 2개일 때의 과정이 두 번 나타난다.

그럼 원판이 3개일 때는 원판이 2번일때의 과정이 두번 나타는 것인가?

그렇다면 다음의 식을 만족하지 않을까? 

3원판 = 2원판(3) * 2  + 1  = 7개

4원판 = 3원판(7) * 2 + 1 = 15개

5원판 = 4원판(15) * 2 + 1 = 31개

 

개수에 대한 규칙을 찾았다.

 

다음 이동에 대한 규칙을 찾아보자

1개일 때 

A의 1원판을 C로 옮긴다.

 

2개일 때

A의 1번원판을 B로 옮기고

A의 2번 원판을 C로 옮기고

B의 1번 원판을 C로 옮긴다.

 

3개 일 때

A의 1원판을  C로 옮기고

A의 2원판을 B로 옮기고

C의 1원판을 B로 옮기고

A의 3원판을 C로 옮기고

B의 1원판을 A로 옮기고

B의 2원판을 C로 옮기고

A의 1원판을 C로 옮긴다.

다음과 같은 규칙을 찾을 수 있었다.

A->B
A->C
B->C

3과정을 거친 다는 것이다.

 

 

 

알고리즘 작성을 시작해보자.

원판이 한개인 경우를 제외하고는

A에서 B로 가는 것 하나

A에서 C로 가는 것 하나 (시작에서 끝으로 이동한다.)

B에서 C로 가는 것 하나

 

그렇다면 하노이 함수에는 시작점과 끝을 알려주는 변수 (A, C)가 있어야할 것이다. 

그리고 중간에 경우해가는 변수 (B)

그리고 원판의 개수를 알려주는 함수

 

 

원판이 3개라 생각하고 작동을 예상해보자.

 

ADT 하노이 (int n, char start, char end, char pass){
	if(n이 1이라면)  //원판이 한개라면
    	출력하세요 ("원판1을 start에서 end로 움직였습니다.", start, end);
        
    else{
    	하노이(n-1, start, pass, end)	// A에서 B로 가는데 C를 이용한다.
        출력하세요 ("원판 n을 start에서 end로 움직였습니다");  // 이 부분은 원판이 3개일 경우로 이해하면 될듯
        하노이(n-1, pass, end, start) // B에서 C로 가는데 A를 이용한다.
	}

}

 

한 번 만들어보자.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

void hanoi(int n, char start, char end, char pass) {
	if (n == 1) {
		printf("원판 %d를 %c에서 %c로 움직였습니다. \n", n, start, end);
	}
	else {
		hanoi(n - 1, start, pass, end);
		printf("원판 %d를 %c에서 %c로 움직였습니다. \n", n, start, end);
		hanoi(n - 1, pass, end, start);
	}
}

int main() {
	int n;
	printf("하노이을 구합니다. 숫자를 입력해주세요.");
	scanf("%d", &n);
	hanoi(n, 'A', 'C', 'B');
}

정상적으로 출력하는 것을 확인한다.

 

그러나 아직 하나가 남았다. 몇번 움직여야 하는지 나오지 않는다.

 

가장 쉬운 것은 전역변수를 선언하고 printf 함수가 선언될 때마다 count++ 되게 하는 것이다.

이를 위해 행번호를 출력하게 만들겠다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int count = 1;

void hanoi(int n, char start, char end, char pass) {
	if (n == 1) {
		printf("%d. 원판 %d를 %c에서 %c로 움직였습니다. \n",count++, n, start, end);
	}
	else {
		hanoi(n - 1, start, pass, end);
		printf("%d. 원판 %d를 %c에서 %c로 움직였습니다. \n", count++, n, start, end);
		hanoi(n - 1, pass, end, start);
	}
}

int main() {
	int n;
	printf("하노이을 구합니다. 숫자를 입력해주세요.");
	scanf("%d", &n);
	hanoi(n, 'A', 'C', 'B');
	printf("%d 번 이동했습니다.", count-1);
}

 

이로서 하노이탑 문제를 마무리한다.