AHRIBORI.COMv0.9
HomeAbout (2)Javascript (7)CSS (12)React (3)Webpack (1)Java (0)Node.js (4)ElasticSearch (1)자료구조 (8)알고리즘 (6)Selenium (1)Linux (2)Docker (1)Git (1)Tip (4)Issue (1)Memo (3)

[알고리즘] 하노이의 탑 (Tower of Hanoi)

아리보리 | 2017.05.26 11:00 | 조회 1295 | 추천 0 | 댓글 0

하노이의 탑 (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번 기둥으로 이동