[백준11729_자바스크립트(javascript)] - 하노이 탑 이동 순서

🔴 문제

하노이 탑 이동 순서

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const n = Number(fs.readFileSync(path));
const answer = [];
let count = 0;
// 하노이탑, 시작, 끝, 보조
function hanoi(n, start, end, sub) {
  count++;
  if (n === 1) {
    answer.push([start, end]);
    return;
  }
  hanoi(n - 1, start, sub, end);
  answer.push([start, end]);
  hanoi(n - 1, sub, end, start);
}

hanoi(n, 1, 3, 2);

console.log(count);
for (const [start, end] of answer) {
  console.log(start, end);
}

🟢 풀이

* 참고자료에 넣어둔 유튜브 링크를 보고 이해한 풀이입니다.

하노이 탑 이동은 동일한 구조가 반복되므로 재귀형태로 풀이한다.
hanoi라는 함수를 만들어 탑의 층수, 시작인덱스, 끝인덱스, 보조 인덱스를 매개변수로 받아 재귀호출을 진행하게 된다.
하노이 재귀함수가 호출된 수를 기억하기 위해 count 변수를 만들어 호출될때마다 값을 증가시켜준 뒤 원반을 옮기는 작업을 한다.

만약 한 층짜리면(n == 1) 어디로든 옮길수 있으므로 그냥 시작 위치의 원반을 끝 위치로 옮겨주면된다. 이 과정을 출력해줘야 하기 때문에 정답 배열에 추가해줬다.

만약 한층짜리가 아니라면 보조로 옮겨야 하는 과정이 반복되므로 재귀함수를 호출해준다. 이때 원반이 5층이라면 마지막 원반을 제외한 상위 4개의 원반을 보조위치로 옮겨줘야 한다.

🔵 Ref

https://www.youtube.com/watch?v=FYCGV6F1NuY&t=7s