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

재귀함수?

재귀함수란 종료 조건이 충족될 때까지 자기 자신을 부르며 반복적으로 작업을 수행하는 함수를 말한다.

백준 11729
사실, 백준에서 하노이 탑 문제를 풀때까지는 내가 재귀함수를 어느 정도 이해하고 있다고 생각했지만 나의 착각이었다.

여러 번의 삽질을 반복한 후, 개념을 확실히 다지는 편이 좋겠다고 생각해서 구글링도 해보고 유튜브에서 영상도 보면서 재귀함수에 대해서 이해하려고 노력을 했다.

워낙 둔해서 그런지 쉽게 이해되지는 않았지만 계속해서 고민해보고, 검색해보면서 정리를 해보았다...

☝🏼.종료조건 설정이 중요하다.

재귀함수는 계속해서 자기 자신을 호출하는 함수이기 때문에 원하는 결과를 얻었을 때 종료하는 조건을 잘 설정을 해야 한다.

✌🏼.문제의 정의를 정확히 표현해야 한다.

문제를 보면 문제의 정의를 어떻게 선언해야 하는지 설명해주는데 이 부분이 중요하다. 집중해서 잘 확인하자!

🤟🏼.반복문보다 느리다.

재귀함수는 반복문보다 느리다. 그렇다면 왜 사용할까? 반복문보다 보기 좋기 때문에 유지보수 측면에서 장점이 있다. 재귀함수를 사용하면 더 보기 좋고 깔끔한 코드 작성이 가능하기 때문.
그렇기 때문에 무작정 재귀함수를 사용하는것은 지양할 것.

"문제의 정의"와 "종료조건"이 핵심이다!

👏 제출한 코드

"use strict";
let input = 0;
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input = Number(line.trim());
  })
  .on("close", () => {
    let count = 0;
    let answer = [];
    function hanoi(num, from, to, other) {
      // num: 원반의 수
      // from: 원반들이 위치한 곳의 번호
      // to: 원반들을 옮길 목적지 번호
      // other: 나머지 한 곳(목적지가 아닌) 곳 번호
      // 모두 옮겼으면 종료
      if (num === 0) {
        return;
      } else {
        // 가장 아래 원반을 제외한 원반들을 재귀적으로 목적지가 아닌 곳으로 옮김
        hanoi(num - 1, from, other, to);
        // 옮기는 과정을 배열에 넣으면서 횟수(count) 증가시키기
        answer.push([from, to]);
        count++;
        // 목적지가 아닌 곳으로 옮겼던 원반들을 재귀적으로 목적지로 옮김
        hanoi(num - 1, other, to, from);
      }
    }
    hanoi(input, 1, 3, 2);
    console.log(count);
    console.log(answer.map((el) => el.join(" ")).join("\n"));
  });

가장 최우선적으로 해야 할 것은 최하층, 제일 큰 원반을 제외하고 다른 원반들을 다른 곳으로 이동시켜야 한다.

그리고나서 가장 큰 원반을 목적지로 옮기면 그 후에는 다른 곳에 있는 원반들을 그 위에 쌓아주면 된다.

✅ 공부하면서 도움을 많이 받은 얄코님 영상