3. 재귀함수 (보충자료 - 하노이 타워)

자료구조 수업시간에 한 번은 꼭 해봤을 '하노이 타워'에 대한 리뷰를 하겠습니다. 

(사실, 안하고 넘어갔는데... 막상 코딩해보려니깐 멘붕)

먼저, 하노이 타워의 동작 원리 뭔저 살펴보면 아래와 같습니다.

  A                            B                            C

A에 있는 원반(1, 2, 3)을 C로 그대로 옮기는 방법을 구하는 문제입니다.

(단, 원반은 한 번에 하나씩만 옮길수 있고, 옮기는 고정에서 작은 원반의 위에 큰 원반이 올려져서는 안됩니다.)

간단히 n = 3일 경우를 생각해보겠습니다.

원반	이동
1	A -> C
2	A -> B
1	C -> B
3	A -> C
1	B -> A
2	B -> C
1	A -> C

위 과정을 거치면, 기존 A에 위치했던 원반들이 모두 C로 그대로 옮겨짐을 확인할 수 있습니다.

One more time, 이번에는 n = 4일 경우를 생각해보겠습니다.

-> 원반 4(제일 밑)의 것을 A에서 C로 이동한 다음, 위에서 실행한 n=3인 경우를 해보겠습니다.

 이를 통해, 하노이탑 문제 또한, 재귀함수를 이용한다는 것을 알 수 있습니다. 1) 재귀함수임을 인지했으니 이제 '종료 조건'을 알아보겠습니다.

2) 종료 조건

 - 원반의 개수(n)가 1이면된다. 또한, 마지막으로 옮기는 원반은 제일 작은 원반(1)이므로 다음과 같이 표현할 수 있습니다.

if(n == 1)

System.out.printf("원반 1을 %c에서 %c로 이동", from, to);

3) 반복 패턴 코드화

- 제일 먼저, 나머지 원반을 A(from) -> B(by) 합니다.

- 다음으로, 제일 큰 원반을 A(from) -> C(to) 합니다.

- 끝으로, 첫번째의 나머지 원반을 B(by) -> C(to) 합니다.

void hanoi(int n, char from, char by, char to) {

.

.

.

else {    // n != 1

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

System.out.printf("원반 %d를 %c에서 %c로 이동", n, from, to);

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

}

}

코드 보기