백준 JS | 11729번 하노이 탑 이동 순서

출처 : 백준 온라인저지

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

✅ Solution

const input = require('fs').readFileSync('/dev/stdin').toString().trim();

const N = Number(input);
const answer = [];
let cnt = 0;

function hanoi(n, from, other, to) {
  if (n === 0) {
    return;
  } else {
    hanoi(n - 1, from, to, other);
    answer.push([from, to]);
    cnt++;
    hanoi(n - 1, other, from, to);
  }
}

hanoi(N, "1", "2", "3");
console.log(cnt);
console.log(answer.map((i) => i.join(" ")).join("\n"));

 

 

이번 문제는 로직을 스스로 생각하지 못하고, 다른 사람의 답안을 참고하였으나

이 역시 재귀함수를 사용해야 했는데, 재귀함수에 대한 이해 부족으로 굉장히 오랜시간 고생했던 문제이다.

ZeroCho 님의 유튜브에서 배웠던 Stack 과 Background 방식으로 이해하고자 했는데 아직 잘 이해가 되지 않았고 아래와 같이 손수 실행될 함수들을 나열하여 이해할 수 있었다. 

위 로직에 따라 실행될 hanoi 함수의 parameter들을 나열한 것이다. 이 함수들을 다시 실행 순서대로 나열하면 아래와 같다. 

이렇게 로직이 어떻게 구현되는지에 대해서는 이해를 했지만, 아직도 문제만 보고 재귀함수를 사용하여 이렇게 로직을 구현하긴 어려울 것 같다. 재귀함수에 대한 더 많은 연습이 필요할 듯..

참고

 

11729. 하노이 탑 이동 순서 - node.js / javascript