[algorithm] 하노이탑 문제

하노이탑 문제는 재귀 알고리즘을 설명하는 데 자주 사용된다.

하노이탑 문제의 규칙

1. 한 번에 하나의 디스크만 옮길 수 있다.
2. 각 이동은 디스크를 한 막대에서 다른 막대로 옮겨야 한다.
3. 어떤 막대 위에도 더 작은 디스크 위에 더 큰 디스크를 놓을 수 없다

재귀적 해결 방법

A에서 C로 3개의 원반을 옮겨야 한다고 생각하면, 가장 큰 문제는 A의 3번째 원반을 C로 옮기는 것이다. 이를 위해서는 1, 2번 원반을 B로 옮겨야 한다. 그 이후 A를 C로 옮겼다고 가정하자.

 

이후 B의 원반들을 C로 옮기기 위한, 생각할 수 있는 가장 큰 문제는 B의 2번째 원반을 C로 옮기는 것이다. 이를 위해서는 B의 첫번째 원반을 A로 옮겨야 한다. 그 이후 B를 C위로 옮긴다고 가정하자.

 

이 상황에서는 A의 원반을 C로 옮기기만 하면 된다.

 

재귀함수는 하위 문제의 결과를 기반으로 현재 문제를 계산하는 패턴에 적합하다.

<큰 문제 부터 생각한 문제 해결 순서> (원반 1, 2, 3 순으로 크기가 커진다고 가정)

원반 1를 A에서 C로 이동 (하기 위해서는 아래 과정이 필요하다.)

원반 2를 B에서 C로 이동 (하기 위해서는 아래 과정이 필요하다.)
원반 1를 B에서 A로 이동 (하기 위해서는 아래 과정이 필요하다.)
원반 3를 A에서 C로 이동 (하기 위해서는 아래 과정이 필요하다.)
원반 1를 C에서 B로 이동 (하기 위해서는 아래 과정이 필요하다.)
원반 2를 A에서 B로 이동 (하기 위해서는 아래 과정이 필요하다.)
원반 1를 A에서 C로 이동

 

<재귀 함수를 실행할 경우, 동작하는 순서>

원반 1를 A에서 C로 이동
원반 2를 A에서 B로 이동
원반 1를 C에서 B로 이동
원반 3를 A에서 C로 이동
원반 1를 B에서 A로 이동
원반 2를 B에서 C로 이동
원반 1를 A에서 C로 이동

 

 

<JavaScript로 구현하기>

function hanoi(count, from, to, temp){
  if (count == 0) return;
  // 2개의 원반을 A에서 C로 이동하는데, B를 사용할 수 있다.
  hanoi(count - 1, from, temp, to);
  console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`)
  // 2개의 원반을 C에서 B로 이동하는데, A를 사용할 수 있다.
  hanoi(count - 1, temp, to, from );
}

// 3개의 원반을 A에서 B로 이동하는데 C를 사용할 수 있다.
hanoi(3, "A", "C", "B")