하노이의 탑

'하노이의 탑', 재귀함수를 배울 때 꼭 거쳐가는 문제라고 한다. 모르는 사람이 있을지 모르겠지만, 간략하게 어떤 놀이인지 살펴보고 간다.
'하노이의 탑'은 기둥이 왼쪽, 가운데, 오른쪽 3개가 있다. 왼쪽 기둥에는 각각 크기가 다른 원반이 정해준 갯수만큼 쌓여있다. 그리고 특징인 것은 큰 원반이 작은 원반 위에 있지 못해서 크기 순으로 쌓여있다는 것이다. 놀이의 진행은 다음과 같다.

1. 모든 원반을 오른쪽 기둥에 옮긴다.
2. 옮기는 과정 중 큰 원반이 작은 원반 위에 있을 수 없다.

주어진 규칙을 가지고 원반을 옮겨야 한다.

문제 풀이 원리

하노이의 탑은 각 단계마다 똑같은 문제를 두 번 풀어야 한다. 조금 더 풀어서 말한다면, 주어진 원반의 탑을 옮기려면 그 이전의 n-1개의 탑을 우선 가운데 고리에 옮겨놓고, n번째 원반을 오른쪽으로 옮긴 후에, 다시 n-1개의 탑을 오른쪽 탑에 옮기면 된다.

1. n-1개의 원반 탑을 가운데 고리에 옮기기.
2. n번째 원반을 오른쪽 기둥에 옮기기.
3. 가운데에 있는 n-1개의 원반 탑을 오른쪽 기둥에 옮기기.

그럼 결국 각각의 단계에서, 시작하는 기둥, 목표 기둥, 비어지는 기둥이 생긴다. 그리고 마지막 1개의 원반을 옮기게 될 때는 그저 목표 기둥에 옮겨주기만 하면 되겠다.

구현

function hanoi(n, from, to, rest){
  	// 재귀식 종료문
    if (n === 1) console.log( `${from} ${to}`);
    else {
      // 우선 n-1 개의 원반을 위에서 걷어낸다.
      // 주의할 점은 n-1 개의 원반이 가야할 곳이 
      // 목적지(to)가 아니라 빈 공간(rest)이다.
      hanoi(n-1, from, rest, to);
      console.log(`${from} ${to}`); // 현재 단계의 원반 옮겨주기
      hanoi(n-1, rest, to, from);
      // 이후 n-1개의 원반을 옮긴 원반에 쌓아주기
    }
}

과거로 돌아가면 나는 이 문제를 다시 풀 수 있을까?(재귀적 사고)

내가 가장 우려하는 바는 위와 같다. 내가 과연 이 풀이를 모른다고 했을 때 돌아가면 해결할 수 있을지 모르겠다.

내가 이번에 하노이 문제를 풀면서 고민했던 부분은 어떻게 이 문제를 추상화할 수 있는지다. 기둥이 3개가 있고, 원반이 $n$개가 있는데, 이를 다 코드로 실체화해야되는 줄 알았다.

그리고 기억을 더듬어서 조금의 힌트를 얻어 from, to, rest의 변수를 써서 활용해야 된다는 것 까지는 알아왔다. 하지만 이곳에서 더 이상 진도가 안 나갔다.

하노이 타워에서 재귀적 사고에 대해서 다시 생각해보게 되었다. 기둥 세 개가 아니라, 시작점-목표점-빈 공간 이라는 사고. n-1개의 탑이 우선 옆으로 옮겨져야 한다는 간단한 통찰. 그리고 이를 재귀로 밀어붙이는 강단. 재귀가 필요한 순간은 딱 이런 순간이 아닐까 싶다.

다시 돌아가도 나는 똑같은 부분에서 막힐 것 같다. 근데 지금 얻는 교훈은 이 문제를 풀면서 알게 된 재귀적으로 풀 수 있는 문제에 대한 느낌인 것 같다.