자료구조 - 하노이 탑(Tower of Hanoi)재귀 호출 코드 구현

하노이 탑 재귀 호출 코드 구현

각각의 기둥을 A, B, C라고 하고 원반의 갯수를 n이라고 하고 문제를 풀어 본다.

 

원반의 갯수가 1인 경우

 

A기둥에 있는 원반을 목표하는 B기둥으옮기기 위해서 (A → B) 이동 횟수 1회가 발생한다.

 

원반 갯수가 2개인 경우

• 원반1 (A → C)
• 원반2 (A → B)
• 원반1 (C → B)

1)A기둥에 원반1,2가 있다. → 2)일단 원반1을 C기둥으로 옮긴다.→ 3)원반2를 B기둥으로 옮긴다. → 4)원반1을 B기둥으로 옮긴다. 이렇게 하면 원반을 모두 목표하는 기둥으로 옮기게 되는데 이때는 3회의 이동 횟수가 발생한다.

 

원반 갯수가 3개인 경우

 

원반의 갯수가 3개여도 (A → C), (A → B), (C → B) 이동 과정을 거쳐 원반1,2가 임시 장소인 C에 가는것과 C에서 다시 목표지점인 B로 가는것 각각 3회씩 2번이 되어 총 이동이 6개가 되어야 한다. 그래야 원반3을 (A→B)로 이동하고 난 후에 원반 3개를 모두 목표하는 기둥으로 옮길 수 있다.

 

다시 정리하면 (A→B)이동 하는 원반3이 제일 큰 원반이 될 것이다. 이 이동이 일어나기 전에 원반1,2를 임시로  C기둥으로 으로 옮기기 위한 이동을 하는데  원반1,2를  두개를 모두 A에서 C로 옮길때 필요한 이동 횟수는 3회다.  3회의 이동으로 원반1,2를 옮기게되면, 가장 큰 원반인 원반3을 (A→B)이동 할수 있게 된다. 이때의 이동 횟수는 1회이다. 그리고 나면 임시로 C기둥에 두었던 원반을 목표 B기둥으로 옮겨야 한다. 이때 역시 필요한 이동횟수는 3회가 된다. 

 

총 원반이 3개일때  7번의 이동으로 원반을 A에서 B로 옮길 수 있다. 

 

원반의 개수가 n개일때

원반이 몇개 이건 Start지점에서 가장 큰 원반이 Goal지점에 오기 전까지는 1,2,3,...,(n-1)의 기둥은 임시기둥에 모두 옮겨져야 한다.  만약 원반의 개수가 5개라면 원반5를 제외한 원반1,2,3,4는 Start기둥에서 임시기둥으로 모두 옮겨져야한다. 이것을 n을 사용해서 나타내면 n개의 기둥을 Start기둥 에서 Goal기둥으로 옮기기 위해서 n-1개의 기둥은 모두 한번은 Start기둥에서 임시기둥으로 옮겨져야 한다. 그래야지만 가장큰 n번째 원반이 Start기둥에서 Goal기둥으로 옮겨질 수 있다. 더불어 이에 해당하는 이동은 꼭 1번은 일어난다고 할 수 있다. 그 이후에 임시기둥으로 모두 옮겨졌던 n-1개의 기둥이 임시기둥에서 Goal기둥으로 모두 옮겨져야. n개의 기둥의 이동이 끝난다. 

이러한 과정을 n을 이용해 도식화 하여 나타내면 f(n) = 1 + 2f(n-1)이된다.  

 

1+2f(n)에 해당하는 함수식

원반의 갯수가 4일때

n = 4 즉 원반의 개수가 4개 일때도 같은 작업이 이루어 져야 한다. n-1개의 원반 모두은 A기둥에서 C기둥으로 옮겨졌다가 n번 째 원반인 원반4가 (A→B) 이동을 하면 다시 n -1개의 원반 모두가 C기둥에서 B기둥으로 옮겨져야한다. n이 4일때  n -1은 3이고 3개의 원반 모두가 특정 기둥에서 다른 기둥으로 옮겨지는데 필요한 이동 7회가 2번 이루어 지니까 3개의 원반들에 대한 14회에 다가 원반4가 하는 이동 1회를 더하면 원반의 갯수가 4일 때 이루어지는 총 이동 횟수는 15회이다. 

 

 

 

[출처 -  하노이탑(Tower of Hanoi) 재귀호출 코드 구현 , 혀니C코딩]

https://www.youtube.com/watch?v=vq7dpFWpwAE