[백준] 11729. 하노이 탑 이동 순서(node.js/javascript/하노이의 탑 알고리즘/코딩테스트/자바스크립트 알고리즘)

[백준] 11729. 하노이 탑 이동 순서

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	34398	16760	13013	48.547%

문제

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

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

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

아래 그림은 원판이 5개인 경우의 예시이다.

입력

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

 

출력

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

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

 

예제 입력 1

3

 

예제 출력 1

7

1 3

1 2

3 2

1 3

2 1

2 3

1 3

 

---

내가 작성한 코드 (자바스크립트)

let fs = require('fs');
let input = fs.readFileSync("/dev/stdin").toString();

let N = Number(input); // 원판의 갯수
let count = 0;
let answer = [];

// num : 원반의 개수
// from : 출발지 기둥 번호
// to : 목적지 기둥 번호
// other : 나머지 기둥 번호

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

원반의 개수가 몇개던 간에, 시작 기둥(from)에서 목표기둥(to)으로 모든 원반을 옮기기 위해서

맨 밑의 원반이 목표 기둥으로 옮겨져야 하는 것은 필수 과정이다.

그 과정이 되기 위해서는 맨 밑의 원반을 제외한 나머지 원반들이 나머지 기둥(other)에 쌓여있어야 한다.

맨 밑의 원반이 시작 기둥(from) -> 목표 기둥(to)으로 옮겨지면, 나머지 원반들이 나머지 기둥(other) -> 목표 기둥(to)으로 옮겨져야 한다.

 

이것을 단계로 나타내보면

1. 맨 밑의 원반을 시작 기둥(from)에서 목표기둥(to)으로 옮긴다.

2. 맨 밑 원반을 제외한 나머지 원반들이 시작 기둥에서 나머지 기둥(other)으로 옮겨져 있어야 한다.

3. 나머지 원반들을 나머지 기둥(other)에서 목표 기둥(to)으로 옮긴다.

 

이렇게 나타낼 수가 있는데 2번 과정이 성립하기 위해서는 계속해서 재귀적으로 만족이 되어야 한다.

(원반이 다섯개라면 처음에 맨 아래 5번 원반을 목표 기둥으로 옮겨야 하고, 그러기 위해서는 나머지 4개의 원반이 나머지 기둥으로 옮겨져 있어야 하는데, 이 때 그게 성립하려면 4번 원반이 목표 기둥으로 옮겨져야 하고, 그러기 위해선 나머지 3개의 원반이 나머지 기둥에 옮겨져 있었어야 하고, 그러려면 3번 원반이 목표 기둥으로 옮겨져야 하고, 그러기 위해선 나머지 2개의 원반이 나머지 기둥에 옮겨져 있었어야 하고, ...... 계속해서 반복되는 재귀라고 생각하면 된다.)

 

따라서 이를 함수로 나타내게 되면

function Hanoi(num, from, other, to){
	if(num === 0)
    	return;
    Hanoi(num - 1, from, to, other);
    console.log(`${from}에서 ${to}로 이동`);
    Hanoi(num - 1, other, from, to);
}

이렇게 되는 것이다. 

재귀 함수가 실행되는 순서는 다음과 같다.