[자료구조] 하노이 타워

자 사진을 보자

 어렸을 때 집에 있었는데 이게 하노이 타워이다.

 

 원반은 한 번에 하나씩만 옮길 수 있고 작은 원반의 위에 큰 원반이 있으면 안된다는 규칙을 가지면서 첫번째 막대기에서 세번째 막대기로 옮기면 된다.

 

자 어떻게 할 것인가?  일단 3개를 가지고 해보자.

 

 

 

 

그림이 불편하게 생겼지만 대충 알아 먹을만 할 것이다.

 

그림에서 규칙을 찾아보면 쉽게 재귀적으로 표현 가능할 것이다.

 

1. 일단 제일 큰 원반 위에 있는 작은 원반들은 모두 두 번째 막대기로 이동시킨다.

2. 그 다음 제일 큰 원반은 세 번째 막대기로 이동시킨다.

3. 두 번째 막대기에 있던 작은 원반들을 세 번째 원반으로 이동시킨다.

 

규칙은 찾았고 이제 프로그래밍 해보자.

 

 

#include <stdio.h>

void Hanoi(int n, char from, char by, char to) {
	if (n == 1)
		printf("%d 번째 원반 %c에서 %c로 이동\n",n,from,to);
	else {
		Hanoi(n - 1, from, to, by); //1번 규칙
		printf("%d 번째 원반 %c에서 %c로 이동\n", n, from, to); //2번 규칙
		Hanoi(n - 1, by, from, to); //3번 규칙
	}
}

int main() {
	Hanoi(3, 'A', 'B', 'C');  //A,B,C는 막대기
}

 

조금 어렵다. 설명이 부족했나?

 

"윤성우의 열혈 자료구조" 이 책을 한번 사서 봐라. 자료구조 기본기 공부하기엔 참 좋은 책인 것 같다.