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

하노이의 탑

코로나로.. 모임 4인 제한이 걸려서 스터디 마지막에 들어간 나는 집에서 따로 알고리즘을 풀었다. 하노이의 탑은 5분만에 이해한 것 같다. 에? 이렇게 하면 되잖아 했더니 한 번에 1장만 이동 가능했고, 에? 그럼 이렇게 하면 되잖아 했더니 작은 원반 위에 큰 원반을 쌓을 수 없었다. 그 다음에 풀었더니 정답. 7번의 순서가 최단 경로였다. 풀면서 영화 혹성탈출의 시저가 된 것 같은 기분이 든 건 나 혼자 뿐이었을까..

알고리즘 코드화

진짜 머리아픈 건 하노이의 탑을 코드로 구현하면서부터였다. 재귀함수의 예로 유명한 하노이의 탑..

function hanoi(n){
  const answer = [];
  
  function frisbee(n, x, y){
    const z = 6-x-y;
    if(n===1) answer.push([x,y]);
    else {
      frisbee(n-1, x, z);
      answer.push([x,y]);
      frisbee(n-1,z,y);
    }
    frisbee(n,1,3);
    return answer;
  }
}

구글링을 해봤을 때 이해에 도움이 되었던 블로그(아래 첨부)가 있었다. 우선 하노이의 탑 코드를 이해하기 위해서는 다음과 같은 이해가 먼저였다.

• '맨 아래 원반'과 '나머지 원반 묶음'이라는 두 분류로 봐야 된다는 것.
• 원반이 n개 이고 기둥이 각각 A,B,C일 때, A n-1 B로, A n C로, B n-1 C로 이렇게 총 세 번의 순서가 필요하다.
• 그리고 제일 중요하다고 개인적으로 생각하는.. 6-x-y에 대한 이해!!!
  6-x-y는 남은 기둥으로 기둥이 3개라고 했을 때, x는 n개의 원반이 존재하는 시작기둥이고 y는 최종적으로 n개의 모든 원반을 이동시킬 기둥이다. 6=x기둥번호+y기둥번호+남은기둥번호 이 식을 정리하면 6-x기둥번호-y기둥번호=남은기둥번호!!!!!
  정리하자면, frisbee(n-1,x,z)는 n-1원반 묶음을 x도아닌 y도아닌 남은 기둥인 z로 옮기는 코드고 frisbee(n-1,z,y)는 n-1원반 묶음을 남은 기둥에서 y로 이동하는 코드이다.

하노이의 탑 코드화에 도움이 되었던 블로그
https://splendidlolli.tistory.com/344