[자료구조] 재귀함수 - 하노이탑에서의 반복 패턴과 문제 해결법

하노이탑의 제약조건은 다음과 같다.

 

- 한 번에 하나의 원판만 이동 가능

- 맨 위에 있는 원판만 이동 가능

- 크기가 작은 원판 위에 큰 원판을 쌓을 수 없음

 

원반 N개를 A에서 C로 이동시키려면, 우선 작은 원반 1개를 A에서 B로 이동시키는 과정이 선행되어야 한다(그래야 마지막 원반을 C에 놓고 다음 프로세스 진행 가능) 그 다음 큰 원반을 A에서 C로 이동시키고, 작은 원반 n-1개를 B에서 C로 이동시킨다.

 

c로 구현시 핵심 코드는 다음과 같다

 

if (n == 1)

   printf("Disk1: %c > %c\n, from, to)

else{

hanoi(n-1,from,to,tmp);

print("Disk%d: %c > %c \n, from, to);

hanoi(n-1,tmp,from,to);

}