하노이의 탑

알고리즘 공부하는데 , 하노이의 탑이라는 유명한 공식이 있다라는 것을 알게 되었고, 재귀함수로 푸는 과정에서 점화식으로 코드로 작성하고, 알아서 잘 작동하는 것이 신기하다. 내 머릿속에서 구현되지 않는 부분이라 정확히 이해가 잘 안됬었다. 한번 정리해보자.

하노이의 탑 규칙

• 한 번에 한개의 원판만 옮길 수 있다.

• 가장 위에 있는 원판만 이동할 수 있다.

• 큰 원판이 작은 원판 위에 있어서는 안 된다.

  하노이의 탑 알고리즘

1. 가장 큰 원판을 c로 옮기기 위해서는 n-1개의 원판이 A에서 B로 가야한다

   
   이동 횟수는 Hanoi(n-1) 이다.

2. 그리고 A에 있는 가장 큰 원판이 C로 이동할 것이다.

가장 큰 원판만 이동하기 때문에 이동하는 횟수는 1회

3. B에 있는 (n-1)개의 원판을 c로 이동한다.

1번과 마찬가지로 Hanoi(n-1) 이다.

An = 2An-1 + 1
An + 1 = 2 (An-1 + 1)

---

bn = An+1
bn+1 = 2bn

b1 = an + 1 = 2
bn = 2^n

---

bn = an + 1 = 2^n
an = 2^n-1

이 수식은 어렸을 때 수1,수2에서 많이 본 것 같다. 내용은 뭐 어렵지 않다.

이제 이것을 재귀 알고리즘에 적용하는 부분이다.

void Hanoi(int N , int start, int mid, int to){

	// 이동할 원반의 수가 1개라면?
	if (N == 1) {
		print(start + " " + to + "\n");
		return;
	} 
 
	// A -> C로 옮긴다고 가정할 떄,
	// STEP 1 : N-1개를 A에서 B로 이동 (= start 지점의 N-1개의 원판을 mid 지점으로 옮긴다.)
	Hanoi(N - 1, start, to, mid);
    
	// STEP 2 : 1개를 A에서 C로 이동 (= start 지점의 N번째 원판을 to지점으로 옮긴다.)
	print(start + " " + to + "\n");
    
	// STEP 3 : N-1개를 B에서 C로 이동 (= mid 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
	Hanoi(N - 1, mid, start, to);
    
}

3개의 경우 손으로 직접 print 되는 부분을 순서대로 적어봤을 때, 답이 맞는것을 확인할 수 있었다.

---

이렇게 풀리는 것이 사실 머리로는 잘 이해가 안된다.. 재귀에 대한 이해도가 부족한 것인지..

Referecne

https://st-lab.tistory.com/96