[CodeKata] 프로그래머스(Lv3) : 하노이의 탑

🥋 Oooth More!! (Level 3) 

 

 

 

🧮 풀이

하노이의 탑 공식을 찾아보니, 아래와 같은 프로세스였다. 이를 재귀함수로 구현하는 것을 못하여 모범답안을 참고하였다.

• A기둥의 (n-1)번째 원판을 B기둥으로 이동시킨다.
• A기둥의 n번째 원판을 C기둥으로 이동시킨다.
• B기둥의 (n-1)번째 원판을 C기둥으로 이동시킨다.

 

 

🖇 리뷰

function solution(n) {
  let answer = [];
  
  const hanoi = (n, start, mid, end) => {
    if (n === 1) answer.push([start,end])
    else {
      hanoi(n-1, start, end, mid)
      answer.push([start,end])
      hanoi(n-1, mid, start, end)
    }
  }
  
  hanoi(n, 1, 2, 3)
  return answer
}

* 출처 : https://after-newmoon.tistory.com/85

• answer는 정답 이동경로들을 누적할 배열이다.
• hanoi()는 하노이의 탑 이동경로를 answer에 누적하는 함수이자, 재귀함수(DFS) 알고리즘을 적용한다. 인자는 n(원판수), start(시작기둥), mid(중간에 거치는 기둥), end(도착기둥) 4개를 받는다.
• n이 1이면 start에서 end로 바로 넘기면 되므로 이를 answer에 push() 한다.
• 아니면, n-1개의 원판을 start에서 mid로 옮긴다.(hanoi() 재귀함수) mid에 원판들을 옮겨놔야, n을 end로 옮기기 때문이다.
• 다음으로, n번째 원판을 start에서 end로 옮겨준다. 이를 answer에 push() 한다.
• 다음으로, mid에 있던 n-1개의 원판을 end로 얹어준다.
• hanoi() 함수 선언이 완료되면, 이를 호출해준다. 인자로는 n과 더불어 1, 2, 3을 각각 시작, 경유, 도착 기둥으로 전달한다.

 

재귀를 어떻게 구현할지 설계하는 부분이 어려웠으나, 막상 그 규칙성을 이해하면 생각보다 재귀함수는 직관적이고 단순하게 작성할 수 있었다.