하노이의 탑 (Tower of Hanoi)

하노이의 탑은 1883년 프랑스의 수학자 루카스가 발표한 게임으로, 규칙은 다음과 같다.

• 3개의 기둥과 크기가 모두 다른 n개의 원판이 있다.
• 원판은 기둥에 꽂을 수 있고 큰 원판은 작은 원판 위에 꽂을 수 없다.
• 세 개의 기둥중 하나에 n개의 원판이 꽂혀있는 상태에서 다른 기둥 중 하나로 이 원판들을 모두 옮겨야 한다.

그림을 보면 쉽게 이해할 수 있다.
다음은 3개의 기둥과 3개의 원판이 있는 하노이의 탑이다.
1번 기둥에 3개의 원판이 꽂혀있는데 이 3개의 원판을 3번 기둥으로 옮기는 순서를 나타낸 것이다.

하노이의 탑을 자바스크립트 코드로 구현해보자

/**
* Tower of Hanoi function
* @param n {number} 원판의 수
* @param from {number} 처음 원판들이 꽂혀있는 기둥 번호 (1~3)
* @param to {number} 원판들을 옮겨야 할 기둥 번호 (from과 다른 기둥번호)
*/
function hanoi(n, from, to) {
	// TODO 하노이의 탑 알고리즘을 구현하세요
	/* 
	   기둥에 있는 원판을 옮길 때 마다
	   "n번 기둥 맨 위의 원판을 m번 기둥으로 이동"
	   이라는 메세지를 console.log로 출력하세요
	*/
    if (n >= 1) {
        const temp = 6 - from - to;
        hanoi(n-1, from, temp);
        console.log(`${from}번 기둥 맨 위의 원판을 ${to}번 기둥으로 이동`);
        hanoi(n-1, temp, to);
    }
}

//--- 실행 ---
hanoi(4, 1, 3); // 4개의 원판을 1번기둥에서 3번기둥으로 모두 옮기자

//--- 실행결과 ---
1번 기둥 맨 위의 원판을 2번 기둥으로 이동

1번 기둥 맨 위의 원판을 3번 기둥으로 이동

2번 기둥 맨 위의 원판을 3번 기둥으로 이동

1번 기둥 맨 위의 원판을 2번 기둥으로 이동

3번 기둥 맨 위의 원판을 1번 기둥으로 이동

3번 기둥 맨 위의 원판을 2번 기둥으로 이동

1번 기둥 맨 위의 원판을 2번 기둥으로 이동

1번 기둥 맨 위의 원판을 3번 기둥으로 이동

2번 기둥 맨 위의 원판을 3번 기둥으로 이동

2번 기둥 맨 위의 원판을 1번 기둥으로 이동

3번 기둥 맨 위의 원판을 1번 기둥으로 이동

2번 기둥 맨 위의 원판을 3번 기둥으로 이동

1번 기둥 맨 위의 원판을 2번 기둥으로 이동

1번 기둥 맨 위의 원판을 3번 기둥으로 이동

2번 기둥 맨 위의 원판을 3번 기둥으로 이동