하노이탑 알고리즘 c언어 - hanoitab algolijeum ceon-eo

Question

하노이 탑(The Tower of Hanoi)은

3개의 막대 중에서 막대 하나에 쌓여 있는 n개의 원판을 다른쪽 막대로 옮기는 게임이다.

단, 아래의 규칙을 지켜야 한다.

1. 한번에 하나의 원판만 이동한다.

2. 맨 위에 있는 원판만 이동한다.

3. 크기가 작은 원판위에 큰 원판을 쌓을 수 없다.

n개의 원판을 옮기기 위해서는 먼저 임시 막대에 n-1개의 원판을 옮긴 후

처음 막대에 남아있는 맨 밑 원판을 목적지 막대에 옮기는 것을 반복한다.

그러고나면 원래 원판이 쌓여있던 막대는 빈 막대가 되고 임시 막대에는 n-1개의 원판이,

목적지 막대에는 가장 큰 원판이 하나 놓여있게 된다.

임시 막대에 있는 원판의 개수를 n으로 다시 설정하고 n-1개의 원판을 원래 원판이 있었던 첫막대에

옮긴다. 임시 막대에 남아있는 원판 하나를 목적지 막대에 옮긴다.

임시막대를 번갈아가면서 계속 반복하면

.

결국 임시 막대에는 제일 작은 원판 하나가 남게 되고, 이 원판을 옮기면

목적지 막대에 원판이 모두 쌓이게 된다.

와! 그러면 엄청 쉬운거 아닌가요?

프로그래밍을 처음 접하는 사람이면 하노이 탑이 첫 난관일 수도 있다.

하나하나 짚어가면서 생각해보면 쉬우니까 포기하지 말고 열심히 해보자.

n개의 원판을 옮기는데 드는 횟수는 (2^n)-1 번.

시간복잡도는 O(2^n)

#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to) {
	if (n == 1) {
		printf("No.1 disk moves from %c to %c\n", from, to);
	}
	else {
		hanoi_tower(n - 1, from, to, tmp);
		printf("No.%d disk moves from %c to %c\n", n, from, to);
		hanoi_tower(n - 1, tmp, from, to);
	}
}
int main() {
	hanoi_tower(3,'A','B','C');
	return 0;
}

하노이 탑의 함수를 만들어줬다.

n은 원판의 갯수고, from은 첫 막대, tmp는 임시 막대, to는 목적지 막대이다.

만약 원판이 하나면 옮기는 것이다.

from에서 to로.

어? 그럼 1은 무조건 from에서 to로 가는게 아닌가요?

코드로만 보면 그렇게 보이겠지만 하노이 탑 함수 안에 들어있는 재귀함수를 보라.

7번째 줄을 보면 from,to,tmp 따위의 막대들의 위치가 바뀌어 인자로 들어간다.

그러면 tmp 위치에는 to가 들어가고 to 위치에는 tmp가 들어간다.

무슨 소리인가 싶겠지만

1이 있는 막대의 위치에 따라서 1이 A 기둥에도 B 기둥에도 C 기둥에도

어디든지 갈 수 있다는 소리다.

main함수 안에 적어놓은 하노이탑 함수의 첫번째 인자의 숫자를 수정하면

다른 개수의 원판이 옮겨지는 과정도 볼 수 있으니 참고하도록 하자.

원판 개수가 3개일 때를 예로 들어 하나하나 따라가 보자면 아래의 사진과 같다.

소스코드에 대한 예시

아래의 설명을 이해하기 쉽게 들여쓰기로 작성했으니 pc버전에서 보길 권장한다.

원판이 3개일 때 hanoi_tower 함수가 작동하는 과정을 볼 수 있다.

hanoi_tower(3,A,B,C)함수가 선언되었다.

else 문에 걸려서 n-1한 후 hanoi_tower(2,A,C,B)로 가준다.

이 함수는 임시 기둥으로 원판을 다 옮겨준다.

여기서 else문이 걸려서 hanoi_tower(1,A,B,C)로 간다.

1일땐 from에서 to로 옮겨주므로

1을 A->C

다시 hanoi_tower(2,A,C,B)로 돌아가 다음 명령을 실행한다.

n과 from to를 출력하는 것이다.

그러면 2번째 원판이 A에서 B로 옮겨진다.

2를 A->B

그 다음 명령문을 실행한다.

hanoi_tower(1,C,A,B)로 간다.

n은 1이므로 C->B

이제 hanoi_tower(2,A,C,B)는 끝났다. hanoi_tower(3,A,B,C)로 돌아간다.

hanoi_tower(3,A,B,C)의 두번째 명령문을 실행한다.

3을 A->C

hanoi_tower(3,A,B,C)의 세번째 명령문을 실행한다.

hanoi_tower(2,B,A,C)에서 else문에 걸린다.

hanoi_tower(1,B,C,A)가 되면 1을 B->A

다시 돌아와서 hanoi_tower(2,B,A,C)의 두번째 명령문을 실행한다.

2 B->C

hanoi_tower(2,B,A,C)의 세번째 명령문이 실행된다.

hanoi_tower(1,A,B,C)

1 A->C

<함수 종료>

출력 결과

코드를 작성한 후에 어떻게 작동하는지 이해가 간다면 잘 따라잡은 것이다.

비교적 쉬웠던 피보나치 수열보다는 조금 복잡할지는 몰라도 순환을 이해하기 위한 기초 중의 기초니까

기반을 잘 다졌으면 좋겠다.

처음 풀어본 알고리즘 문제인데 이틀이 꼬박 걸렸습니다. 그런데 모범답안보니 너무 간단하네요. ㅠ 하노이탑 이동 원리를 아는 것 자체는 사실 무의미하지만 이 문제를 푸는 사고 과정 자체가 확립 되는 것이 중요할 것 같습니다. 머리 좋은 사람 참 많네요. 전 모범답안 보고도 한참 헤맸는데..

재귀함수가 모두 그렇듯, 키 포인트는 함수 자체가 계속 부분집합으로 발생했다 없어지는 방식이라는 것입니다. 일반적인 사고 방식과 같이(저처럼..) 전체를 보면서 풀어나가면 답이 없습니다. 제가 이틀 걸려 짠 코드는 가장 아랫쪽에 남겨둡니다. 흑역사네요. 간단히 3개짜리 원판 옮기기 구조만 보면 나머지는 로직만 주고 컴퓨터에게 맡길 수 있습니다. 실제로 원판이 7개쯤 되면 손으로 그리기도 힘듭니다.

세 개짜리 원판에서 가장 아래쪽에 있는 3이 목적지인 Z로 가기 위해서는 그 위의 숫자들을 전부 Y로 보내야 합니다.

3은 그 위가 Y로 모두 이동하고 나면 Z로 가면 되니 없는 셈 치고 두 개짜리만 신경씁니다. 2개보다 더 많을 때는 손으로 그리기도 꽤 힘든데 2개만 있을 때는 아주 간단히 3단계면 이동이 가능합니다.

즉 원판이 3개(n개) 있을 때, 그 위의 2개(n-1)을 최종 목적지 반대방향으로 이동시켜 준 후 3이 이동하면 된다는 의미입니다. 이 과정을 함수로 표현해보면 아래와 같습니다.

move함수 (이동할 원판 갯수, 출발지, 목적지, 나머지)

결국 최종적으로 원판이 2개만 있는 함수까지 재귀적으로 계속 들어갑니다.

쭉쭉 타고 들어가다가 마지막에 도달하면, 1의 경로를 찍어주고 리턴시킵니다. 재귀함수 탈출 구문입니다. 1에서 출력하고 리턴시키는 이유는 2개의 덩어리가 한 쌍이기 때문입니다. 원판 갯수가 한 개만 들어올 때는 재귀함수 실행 이전에 탈출구문에서 경로를 찍어주고 탈출하기 때문에 2개 단위로 구성해도 문제가 없습니다. 해보시면 알겠지만 2개 단위일 때 세 번의 단계가 있기 때문에 한 개단위로는 경로를 올바르게 순서대로 찍을 수가 없습니다.

마지막 함수가 리턴되면 1이 Z에 가 있게 되고 이제 2가 Y로 가야하는 차례이기 때문에 이 경로를 출력해줍니다.

그리고 다시 마지막 순서를 수행합니다. 원판 갯수가 현재 2개짜리인 함수에 있으니까 원판 갯수를 하나 줄여주고(count - 1), 순서를 Z→Y로 바라보게 만들어 줍니다. 다시 count == 1인 함수가 실행됐고 탈출 구문에 걸려서 경로를 출력하고 리턴됩니다.

이제 count==2의 함수도 끝에 도달했으므로 리턴되고 count==3의 함수로 돌아갑니다.

이제 count==3 함수에서 다음 차례가 실행됩니다. X→Z경로를 출력 한 후, 다시 반대경로(Y)에 있는 숫자를 Z로 보내주는 함수를 실행합니다.

이제 Y→Z로 다시 함수가 실행되면 위의 과정을 반복하고, 모두 리턴되면 첫 함수인 count==3은 최종 리턴되어 재귀함수가 종료됩니다. 로직이 완성되었으므로 이제 count에 무슨 숫자를 넣어도 컴퓨터가 알아서 계산해서 출력해줍니다.

알고나면 위의 로직은 참 간단합니다. 하지만 그 "아는 것"까지가 어려운 것 같습니다. 저만 그런가요..? ㅎㅎ 하노이 알고리즘같은건 사실 몰라도 무방합니다만, 위의 과정을 추론해내는 사고력이 문제가 되겠네요. 항상 아래 과정으로 생각하는 사고 구조가 필요할 것 같습니다.

무언가 같은 내용이 반복된다.
일정한 순서대로 반복되는 것이 아닌, 앞의 내용에 영향을 받아서 기준이 달라지며 반복된다.
재귀함수를 의심한다.
커다란 로직을 최대한 작게 쪼개본다.
최소한으로 쪼개진 단위에 일정한 규칙이 있고, 이 규칙이 큰 단위에도 그대로 적용된다.
최소한의 규칙에 맞게 재귀함수를 짠다.

아래 코드는 백준 알고리즘 제출용으로 약간 수정된 코드입니다. 사이트에 올릴 때는 제약이 많네요. 일단 최종 횟수를 제일 위에 출력해야하는데 함수가 끝나봐야 알 수 있어서 gotoxy()함수로 위에다 출력하려니 컴파일 에러가 뜹니다. 또 scanf_s()함수를 써도 컴파일 에러가 뜨네요. 제출하는 것만 엄청 헤맸습니다.

※ 백준 알고리즘 채점 제출 시 유의사항
1. scanf_s() 함수는 컴파일 에러가 뜬다. (다른 _s함수도 비슷한 가능성이 높음)
2. windows.h 전처리기 삽입 시에도 컴파일 에러가 뜬다.
3. 입력 범위가 지정된 경우, 이에 대한 처리를 해주지 않으면 런타임 에러가 뜬다.

그래서 그냥 아래처럼 함수를 두 번 돌려서 한 번은 카운트만 하고 한번은 출력만 하는 것으로 하니 정답 처리 되는군요. 뭔가 다른 방법이 있을 것도 같지만 그냥 여기까지만 하겠습니다. 중요한 건 제출이 아니니까요..!

#include <stdio.h>

int move_count;

/* 탑 옮기기 카운트용 */
/* parameter : 원판 갯수, 출발지, 도착지, 그 외 */
/* return : void */
void move(int count, int from, int to, int x)
{
	/* 마지막 도달 시 재귀함수 탈출(마지막에서만 실행) */
	if (count <= 1) {
		move_count++;
		return;  // 가장 윗부분(1)에 도달하면 경로 출력 후 리턴
	}

	/* 마지막 도달 전 */
	move(count - 1, from, x, to);  // 바로 윗 숫자 덩어리는 도착지가 바뀜
	move_count++;
	move(count - 1, x, to, from);
}


/* 탑 옮기기 */
/* parameter : 원판 갯수, 출발지, 도착지, 그 외 */
/* return : void */
void move2(int count, int from, int to, int x)
{
	/* 마지막 도달 시 재귀함수 탈출(마지막에서만 실행) */
	if (count <= 1) {
		printf("%d %d\n", from, to);
		return;  // 가장 윗부분(1)에 도달하면 경로 출력 후 리턴
	}

	/* 마지막 도달 전 */
	move2(count - 1, from, x, to);  // 바로 윗 숫자 덩어리는 도착지가 바뀜
	printf("%d %d\n", from, to);  // 현재 경로를 출력
	move2(count - 1, x, to, from);
}


int main()
{
	int count;
	scanf("%d", &count);
	if (count < 1 || count > 20)
		return 0;
	move_count = 0;
	move(count, 1, 3, 2);  // 최종 횟수 카운트
	printf("%d\n", move_count);  // 최종 횟수 출력
	move2(count, 1, 3, 2);  // 최초 1→3번으로 출발	

	return 0;
}

아래는 처음 짠 코드입니다. 실제로 배열에 값을 넣어서 옮기면서 수행하느라 코드가 지저분한데다 로직도 너무 복잡하네요. 그래도 결과는 일단 동일하게 나오긴 합니다.ㅋ 혹시 어렵다 느끼시는 분들은 아래 코드를 보면서 위안을 느끼시길..

#include <stdio.h>

void move_tower(int a, int b, int c);
int counter(int arr[][20], int a, int c, int x, int z);
void index_p(int a, int b, int c, int** x, int** y, int** z);
int comp(int arr[][20], int source, int dest);
void move(int arr[][20], int source, int dest);


int move_count;
int count;
int n;  // 1번 장대 최초 원판 갯수 ( 1<= n <= 20)
int i;  // 2번 장대 원판 갯수
int j;  // 3번 장대 원판 갯수

/* 장대 3개 배열 생성 */
int arr[3][20];

int main()
{
	count = 1;
	while (count <= 20) {
		/* 각 배열 인덱스 */
		i = 0;
		j = 0;
		n = count;
		move_count = 0;

		/* 배열 초기화 */
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 20; j++)
				arr[i][j] = 21;

		/* 초기 원판 값 입력 */
		for (int i = count, j = 0; i > 0; i--, j++)
			arr[0][j] = i;
		
		/* 2의 count제곱 구하기 */
		int square = 1;
		for (int i = 0; i < count; i++)
			square *= 2;

		/* 탑 옮기기 수행 */
		move_tower(0, 2, 1);
		printf("%d개 원판일 때  : %d번 (2^count-1 = %d)\n", 
			count, move_count, square - 1);		
		count++;
	}

	return 0;
}


/* 원판 옮기기 */
/* parameter : 배열 arr, */
/* return : void */
void move_tower(int a, int b, int c)
{
	/* 해당 배열 짝을 맞추기 위한 포인터 생성 */
	int* x = NULL, * y = NULL, * z = NULL;
	index_p(a, b, c, &x, &y, &z);
	if (x == NULL || y == NULL || z == NULL)  // Waring 방지
		return;
	
	
	/* 갯수 기준은 이전 c에서 이동해야할 숫자보다 작은 숫자 */
	int a_counter = counter(arr, a, c, *x, *z);
	int temp;  // 재귀 함수 실행 후 다른곳에서 옮겨오거나 옮겨간 원판 갯수 조정 
	
	while (a_counter > 0) {
		
		if (a_counter % 2 == 1) {  // 홀수라면 이동해야할 방향으로 이동

			// 가능하면 이동
			if ((*y > 0 && arr[a][*x - 1] < arr[b][*y - 1]) || *y == 0) {	
				move_count++;
				move(arr, a, b);
				a_counter--;  // 카운터(갯수) 감소
			}
			else {  // 불가능하면 기준을 바꿔서 다시 수행
				temp = *x;
				move_tower(b, c, a);
				a_counter += (*x - temp);
			}
		}

		else if (a_counter % 2 == 0) {  // 짝수라면 이동해야할 방향 반대로 이동
			
			// 가능하면 이동
			if ((*z > 0 && arr[a][*x - 1] < arr[c][*z - 1]) || *z == 0) {	
				move_count++;
				move(arr, a, c);
				a_counter--;
			}
			else {  // 불가능하면 기준을 바꿔서 다시 수행
				temp = *x;
				move_tower(c, b, a);
				a_counter += (*x - temp);
			}
		}
	}
	if (j >= count)  // 2번 장대에 모든 원판이 가면 재귀함수 종료
		return;

	if (i == 0)  // 1번 장대가 모두 비었다면 0번 장대로 가서 재수행
		move_tower(0, 2, 1);
	else if (n == 0)  // 0번 장대가 모두 비었다면 1번 장대로 가서 재수행
		move_tower(1, 2, 0);
}

/* c보다 작은 a의 갯수 */
/* parameter : 배열인덱스 a,c와 해당 인덱스 넘버 */
/* return : c보다 작은 a의 갯수 */
int counter(int arr[][20], int a, int c, int x, int z)
{
	int i, count;
	for (i = 0; i < x; i++) {
		if (z == 0)
			break;
		if (arr[a][i] < arr[c][z - 1])
			break;
	}

	return (count = x - i);
}


/* 배열 인덱스에 따른 인덱스 값 포인터 변수 생성 */
/* parameter : 인덱스 a,b,c, 인덱스 더블 포인터 x, y, z */
/* return : void */
void index_p(int a, int b, int c, int** x, int**y, int** z)
{
	if (a == 0) *x = &n;
	else if (a == 1) *x = &i;
	else if (a == 2) *x = &j;
	if (b == 0) *y = &n;
	else if (b == 1) *y = &i;
	else if (b == 2) *y = &j;
	if (c == 0) *z = &n;
	else if (c == 1) *z = &i;
	else if (c == 2) *z = &j;
}


/* 이동 가능 비교 */
/* parameter : 비교할 장대 source, dest */
/* return : 가능 == 0, 불가능 == 1 */
int comp(int arr[][20], int source, int dest)
{
	/* 하나도 없을 경우을 대비해서 미리 만들어줌 */
	int x, y, z;
	if (n > 0)
		x = n - 1;
	else x = n;

	if (i > 0)
		y = i - 1;
	else y = i;

	if (j > 0)
		z = j - 1;
	else z = j;


	/* 비교 */
	if (source == 0) {
		if (dest == 1) {
			if (arr[0][x] < arr[1][y])
				return 0;
			else return 1;
		}
		else {
			if (arr[0][x] < arr[2][y])
				return 0;
			else return 1;
		}
	}
	else if (source == 1) {
		if (dest == 0) {
			if (arr[1][y] < arr[0][x])
				return 0;
			else return 1;
		}
		else {
			if (arr[1][y] < arr[2][z])
				return 0;
			else return 1;
		}
	}
	
	else if (source == 2) {
		if (dest == 0) {
			if (arr[2][z] < arr[0][x])
				return 0;
			else return 1;
		}
		else {
			if (arr[2][z] < arr[1][y])
				return 0;
			else return 1;
		}
	}
	return 1;
}

/* source에서 dest로 하나 옮겨줌 */
/* parameter : 옮길 장대 source, dest */
/* return : void */
void move(int arr[][20], int source, int dest)
{
	if (source == 0 && n > 0) {
		if (dest == 1) {
			arr[1][i++] = arr[0][--n];
			arr[0][n] = 21;
		}
		else if (dest == 2) {
			arr[2][j++] = arr[0][--n];
			arr[0][n] = 21;
		}
	}

	else if (source == 1 && i > 0) {
		if (dest == 0) {
			arr[0][n++] = arr[1][--i];
			arr[1][i] = 21;
		}
		else if (dest == 2) {
			arr[2][j++] = arr[1][--i];
			arr[1][i] = 21;
		}
	}

	else if (source == 2 && j > 0) {
		if (dest == 0) {
			arr[0][n++] = arr[2][--j];
			arr[2][j] = 21;
		}
		else if (dest == 1) {
			arr[1][i++] = arr[2][--j];
			arr[2][j] = 21;
		}
	}
}