하노이의 탑

세 개의 기둥과 크기가 서로 다른 원판이 있다. 처음에는 아래 그림처럼 기둥 A에 원판이 작은 것이 위로 오도록 쌓여 있다. 게임의 목적은 처음에 꽂혀 있던 순서대로 기둥 C에 옮겨서 쌓는 것이다. 다음 규칙들을 만족하면서 움직여야한다.

1. 원판은 한 번에 한 개만 이동할 수 있다.
2. 큰 원판은 작은 원판 위에 있을 수 없다.
3. 최소한의 횟수로 원판을 이동해야 한다.

하노이의 탑은 재귀 호출의 대표적인 문제이다. 총 원판 갯수를 n이라 할 때, n = 1, 2, 4인 경우를 예시로 살펴보자.

1. n = 1

기둥 A에서 기둥 C로 옮기면 문제가 해결된다.

1번 원판을 A에서 C로 이동한다.

2. n = 2

큰 원판은 항상 작은 원판보다 아래에 있어야 한다는걸 생각하자. 큰 원판을 C로 옮기려면 먼저 작은 원판을 B로 먼저 옮겨야 한다. 그 뒤에 큰 원판을 C로 옮기고, 작은 원판을 C로 옮기면 마무리된다.

1번 원판을 A에서 B로 이동한다.
2번 원판을 A에서 C로 이동한다.
1번 원판을 B에서 C로 이동한다.

3. n = 4

위 그림은 n=4일 때, 가장 큰 원판을 A에서 C로 옮기는 과정이다. 유심히 봐야할 부분은 8번이다. 1~8번 과정을 거치면서 가장 큰 원판을 제외하고 나머지 원판을 순서대로 B에 쌓아놓았다. 그리고 9번으로 넘어가서 A에 있는 4번 원판을 C로 옮겨보자. 그러면, n=3인 하노이의 문제를 풀어야하는 상황이 나온다.

3개의 원판을 A에서 B로 이동한다.
4번 원판을 A에서 C로 이동한다.
3개의 원판을 B에서 C로 이동한다.

하노이의 문제를 해결하는 함수를 hanoi(n, from, via, to)라고 하자. n은 원판의 총 갯수, from은 출발지, via는 경유지, to는 목적지라고 하면, n = 4인 경우는 다음과 같이 나타낼 수 있다.

hanoi(4, A, B, C) = hanoi(3, A, C, B) + hanoi(1, A, B, C) + hanoi(3, B, A, C)

hanoi(1, from, via, to)는 1이므로, n일 때 함수를 다음과 같이 정리할 수 있다.

hanoi(n, from, via, to) = hanoi(n-1, from, to, via) + 1 + hanoi(n-1, via, from, to)

4. 함수구현

문제 주소: https://programmers.co.kr/learn/courses/30/lessons/12946?language=javascript#

다음은 프로그래머스에 나온 알고리즘 문제를 일부 변형한 해답이다. 문제에서는 이동경로만 배열로 제시하도록 했는데, 어떤 원반이 이동했는지 알 수 있도록 수정했다.

function solution(n) {
const result = [];
  function hanoi(n, from, via, to) {
    if ( n === 1) {
      result.push([n, from, to]); // base case: 1번 원반이 from에서 to로 이동
    }
    else {
      hanoi(n-1, from, to, via);
      result.push([n, from, to]); // recursion: n번 원반이 from에서 to로 이동
      hanoi(n-1, via, from, to);
    };
};
hanoi(n, "A", "B", "C"); 
return result;
};