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

출처

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

문제

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

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

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

풀이

재귀하면 빼놓을 수 없는 유명한 하노이탑 문제.
다른 문제들과 마찬가지로 케이스를 나눠서 생각해 보았다.

일단 n = 1일 때를 살펴보자. n = 1일 때는 바로 목적지로 옮기면 되므로 from,to를 그대로 출력해 주면 된다.

하지만 n >= 2 부터는 약간 말이 달라진다.
왜냐하면 하노이 탑의 규칙이 적용되기 때문이다.
n = 2를 살펴보자. 맨 위에 있는 원판을 가운데로 옮겨야 가장 아래에 있는 원판을 옮길 수 있게 된다.

그렇다면 n = 3일 경우는 어떨까? 원판 3개의 경우 마지막 원판을 옮기기 위해서는 위에 있는 두 개의 원판을 가운데로 옮겨야 한다. 따라서 재귀함수를 호출해 준다. 여기서 아까 한 것이 생각나지 않는가? 그렇다면 n = 2가 된다. 즉, 두 개의 원판을 옮기는 경우로 계산되는 것이다. 계산이 완료되면, 가장아래 원판을 목적지로 옮겨주고 가운데에 있는 두 개의 원판을 목적지로 옮겨주면 하노이 탑이 완성되게 된다. 다만 이렇게 매번 출력을 하면 시간초과가 나므로 배열에 값을 저장하자.

마지막으로 실행 횟수의 규칙을 찾아보자.
n = 1 - 1
n = 2 - 3
n = 3 - 7
따라서 n = k 개라면 실행 횟수는 2^k - 1이 된다.

코드

const input = Number(require('fs').readFileSync('/dev/stdin').toString());
let arr = [];
const move = (n,from,to) => {
    let middle = 6 - from - to;
    if (n == 1) {
        arr.push([from, to]);
    }
    if (n >= 2) {
        move(n - 1,from,middle);
        move(1,from,to);
        move(n-1,middle,to);
    }
}
move(input,1,3);
console.log(Math.pow(2,input) - 1);
console.log(arr.map((e) => e.join(' ')).join('\n'));