Skip to main content

11729. 하노이 탑 이동 순서

Solution​

// For Submit
const input = `${require("fs").readFileSync("/dev/stdin")}`.trim().split("\n"); // " " | "\n"]

// My Code
const solution = (input: string[]): string => {
  // Initial Setting
  const N = parseInt(input[0]);
  let moves: string[] = [];

  const hanoi = (n: number, from: number, to: number, aux: number): void => {
    // 원판이 하나일 때, 목표로 이동
    if (n === 1) {
      moves.push(`${from} ${to}`);
      return;
    }

    hanoi(n - 1, from, aux, to); // n-1개의 탑을 여분의 공간에 옮김
    moves.push(`${from} ${to}`); // n번째 탑을 옮김
    hanoi(n - 1, aux, to, from); // 다시 n-1개의 탑을 도착지로 옮김
  };

  // Logic
  hanoi(N, 1, 3, 2);

  return `${moves.length}\n${moves.join("\n")}`;
};

console.log(solution(input));

Solution Walkthrough​

  • hanoi 해당 함수를 재귀 하면서 푸는 방식이다.

Go to Problem​

Solve Baekjoon 11729