자료구조와 알고리즘 인강 정리 : 재귀-하노이탑

하노이탑 게임

: 한 수학자가 개발한 게임으로 세개의 기둥과 서로 다른 크기의 원반이 있으며 이 원반은 위로 갈수록 작은 원반으로 이루어져 있다. 하나의 기둥에 있는 원반들을 다른 기둥으로 옮겨야하는데 이때 아래의 규칙을 준수해야한다.

1. 한 번에 하나의 원반을 움직일 수 있다.

2. 가장 위에 있는 원반만 옮길 수 있다.

3. 아래에 작은 원반이 올 수 없다.

 

• 하노이탑을 하향식 방식으로 접근 후 계산 (순서대로 스택에 하나씩 쌓인다.)
  기둥 A에 있는 원반 1,2,3을 기둥 c로 옮기려고 함.
  스택1 : 원반3을 기둥 C로 옮김
  스택2 : 원반2,1을 기둥 B로 옮김(하위문제)
  스택3 : 원반 2,1을 기둥 B로 옮기기 위해서는 원반1이 기둥 C로 이동해야함. -> 바로 C로 이동시킬 수 있으므로 더 이상 하위문제가 없음.-> 스택에서 하나씩 꺼내서 해결
  
  스택1 : 기둥 B에 있는 원반2,1을 기둥 C로 이동
  스택2 : 기둥 B에 있는 원반 2를 기둥 C로 이동시켜야함. (하위문제)
  스택3 : 원반1을 기둥 A로 옮긴다. -> 바로 A로 옮길 수 있으므로 더 이상 하위문제가 없음 -> 스택에서 하나씩 꺼내서 해결

hanoi.mjs

terminal

 

하노이탑 재귀함수 풀이