알고리즘 #55 (하노이탑)

• 출처 - https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/

하노이 탑의 문제를 해결할 때 중요한 것은, 이 하노이 탑은 재귀함수 를 사용 해야한다는 것이다.

먼저 위의 그림을 보도록 하자.

원반이 3개 일때,

• [1번째] 제일 큰 원반이 C로 가야한다.

• 그러기 위해선, 중간원반 작은원반이 B로 가야한다.

• 큰 원반을 고려하지 않고 원반 2개를시작점 'A' 와 보조고리 'C' 를 이용하여, 도착지 'B' 로 이동하는 것을 고려해야 한다.

• 작은 2원반이 B로 옮겨갔으면, 제일 큰 원반을 C 로 옮긴다.

  이렇게 하면 B고리에 작은 원반 2개가 있을 것이다 [그림4]

그럼 작은 원반의 고리 2 개를 시작점 'B' 와 보조고리 'A' 를 이용하여, 도착지 'C' 로 이동하는 것을 고려해야 한다.

원반이 1개 일 땐,
1. 시작점 'A' 에서 도착지 'C'로 바로 옮기면 된다.

원빈이 2개 일 땐,
1. (원반이 1개 일 때 처럼) 작은 원반을 B로 옮기는 것
2. (원반이 1개 일 때 처럼) 큰 원반을 C로 옮긴다.
3. (원반이 1개 일 때 처럼) 작은 원반을 다시 C로 옮긴다.

그러면, 원반이 3개 일 땐,
원반이 2개 일 때를 이용하여 (1번 원반, 2번 원반)을 A에서 B로 옮기고,

원반이 1개 일 때를 이용하여 3번원반을 C로 옮기고

원반이 2개 일 때를 이용하여 (1번 원반, 2번 원반)을 B에서 C로 옮기면 된다.

원반이 N 개 일 떈,
1. (원반이 N-1개 일 때 처럼) N-1개의 원반을 B로 옮긴다.
2. 원반이 1개 일 때 처럼 마지막 원반을 C로 옮기고.
3. (원반이 N-1개 일 때 처럼) N-1개의 원반을 B에서 C로 옮긴다.

코드로 표현 하게 되면,

function path(N, START, GOAL) => {
	console.log((`'${N}'원반을 ${START}에서 ${GOAL}로`))
}

function hanoi(N, START, GOAL, ASSISTANT) => {
  if(N === 1) {
     path(N, START, GOAL)
 } else {
  	hanoi(N-1, START, ASSISTANT, GOAL) 
	  // N-1개의 원반을 A->B 로 보조 기둥 c를 이용하여 옮긴다.
 	path(N, START, GOAL)
  	// 제일 큰 원반을 A->C 로 옮긴다
  	hanoi(N-1, ASSISTANT, GOAL, START)
 	 // N-1개의 원반을 B->C 로 보조 기둥 A를 이용하여 옮긴다.
	}
}
 hanoi(3, 'A', 'C', 'B') 

'1'원반을 A에서 C로 // 1
'2'원반을 A에서 B로 // 2
'1'원반을 C에서 B로 // 3
'3'원반을 A에서 C로 // 4
'1'원반을 B에서 A로 // 5
'2'원반을 B에서 C로 // 6
'1'원반을 A에서 C로 // 7