하노이의 탑(Towers of Hanoi)

References

이번 글은 아래 자료들을 참고하여 작성하였습니다.
1. Towers of Hanoi on Khan Academy
2. [파이썬]알고리즘 이야기(01. 하노이 탑) by 파이썬 클래쓰 on Youtube
3. 무조건 이해시켜 드립니다. 비법 대방출! 재귀 알고리즘 Recursion - 하노이탑, 피보나치 수열 by 딩코딩 on Youtube

들어가며

하노이의 탑을 풀기 위해서는 우선 재귀 함수에 대한 이해가 필요하다. 재귀 함수는 javascript의 일반적인 동작 방식인 명령형(Imperative)이 아니라 선언형(declarative)으로 동작한다. 따라서 재귀 함수를 온전히 이해하려면 declarative programming에 대한 감각이 필요하다.

재귀 함수를 짤 때 중요한 것은 두 가지이다.

1. 종료 조건
2. 문제 정의

그럼 위 두 가지를 고려하여 하노이의 탑의 pseudo code를 나열해보자.

• 종료조건
  1.원반이 하나 남으면 끝
• 문제 정의 선언
  1. N개의 원반을 옮기기 위해서는 N-1개의 원반을 temp기둥으로 옮겨야 함.
  2. N번째 원반을 목적지 기둥으로 옮긴다.
  3. temp기둥에 있는 N-1개의 원반을 목적지 기둥으로 옮긴다.

위의 pseudo code를 바탕으로 코드를 짜면 아래와 같다.

Towers of Hanoi

const route = [];

function hanoi(num, from, to, temp) {
  //원판이 한 개일 때에는 바로 옮기면 됨.
  //종료조건
  if (num === 1) {
    route.push([from, to]);
    return NaN;
  }

  hanoi(num - 1, from, temp, to); // n - 1개의 원반을 temp기둥에 옮김. 따라서 to -> temp, temp -> to 로 변경
  route.push([from, to]); // n번째 원반을 from기둥에서 to기둥으로 옮김. n번째 원반을 막고 있던 n - 1개의 원반을 temp로 다 옮겼기 때문에 가능.
  hanoi(num - 1, temp, to, from); // temp기둥에 있던 n - 1개의 원반을 to기둥으로 옮김. temp -> from, from -> temp 로 변경.
}
hanoi(3, "A", "B", "C");
console.log(route); 
/*
[
 [ 'A', 'B' ],
 [ 'A', 'C' ],
 [ 'B', 'C' ],
 [ 'A', 'B' ],
 [ 'C', 'A' ],
 [ 'C', 'B' ],
 [ 'A', 'B' ]
]
*/
console.log(route.length); // 7

위 코드는 아래와 같은 순서로 실행된다.

실행 과정(7단계)

hanoi(3, A, B, C); // 4. push A, B: 3번 원반 from(A)에서 to(B)로 이동
	hanoi(2, A, C, B) // 2. push A, C: 2번 원반 from(A)에서 temp(C)로 이동
		hanoi(1, A, B, C) // 1. push A, B: 1번 원반 from(A)에서 to(B)로 이동
		hanoi(1, B, C, A) // 3. push B, C: 1번 원반 to(B)에서 temp(C)로 옮겨서 2번 원반 위에 쌓기
	hanoi(2, C, B, A)  // 6. push C, B: 2번 원반 temp(C)에서  to(B)로 이동
		hanoi(1, C, A, B) // 5. push C, A: 2번 위에 있던 1번 원반 temp(C)에서 from(A)로 이동
		hanoi(1, A, B, C) // 7. push A, B: 1번 원반 from(A)에서 to(B)로 이동하면서 완성.

위 실행 순서를 그림으로 나타내면 다음과 같다.

함께 보기

recursive algorithms