하노이 탑 이동 순서 (11729번) [node.js, JavaScript]

하노이 탑 이동 순서 (11729번) [node.js, JavaScript]

하노이 탑 이동 순서 (11729번) [node.js, JavaScript]

문제 설명

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.

쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

의사코드

Hanoi 함수는 원판의 개수, 시작 장대, 도착 장대, 보조 장대를 인자로 받아 호출합니다. 재귀함수의 종료 조건은 원판의 개수인 num이 1개가 될 때 시작 장대와 도착 장대 번호를 answer에 문자로 추가하고 함수가 종료됩니다. 예를 들어 3개 원판 있는 하노이 탑의 이동하기 위해서는 맨 아래 있는 큰 원판을 3번째 장대로 옮겨야 한다. 그렇다는 말은 맨 아래 원판을 제외한 나머지 2개 수의 원판을 모두 보조 장대인 2번으로 옮겨야 한다는 것입니다. 이것을 Hanoi(2, 1, 2, 3); 으로 명령합니다. Hanoi(2, 1, 2, 3); 호출되었을 때는 2개의 원판만을 생각합니다. 1번 장대에 모든 원판을 2번 장대로 옮겨야 하는데 1번에 맨 아래에 깔린 원판을 먼저 옮기기 위해서는 맨 위에 있는 원판을 2번 장대가 아닌 3번 장대로 먼저 옮겨야 하므로 Hanoi(1, 1, 3, 2); 명령어가 수행되고 num가 1이기 때문에 더 이상 재귀호출 하지 않고 종료가 됩니다. 다시 Hanoi(2, 1, 2, 3); 이 호출되었던 시점으로 돌아와서 2번째 원판을 2번 장대로 옮기고, 3번째 장대로 옮겼던 1번째 원판을 다시 2번 장대로 옮겨야 하므로 Hanoi(1, 3, 2, 1)가 호출됩니다. 2,3,4번 과정처럼 재귀 호출되면서 원판을 하나씩 도착장대로 모두 옮기게 됩니다.

Code

const input = require("fs").readFileSync("/dev/stdin").toString().split("

"); const N = Number(input[0]); const answer = []; function Hanoi(num, from, to, other){ if (num === 1) { answer.push(`${from} ${to}`); return; }else{ // 받아온 원반 갯수보다 하나 적은 원반들을 목적지가 아닌 곳으로 재귀적으로 이동 Hanoi(num - 1 , from, other, to); // 맨 아래 원반을 목적지로 이동시킴 answer.push(`${from} ${to}`); //다른 곳으로 옮겼던 원반들을 그 위에 얹음 Hanoi(num - 1, other, to, from); } } Hanoi(N, 1, 3, 2); console.log(answer.length); console.log(answer.join("

"));

from http://jinblog123.tistory.com/225 by ccl(A) rewrite - 2021-11-23 23:27:31