[백준] 1914번 - 하노이 탑 (JavaScript)

 

 

---

 

문제

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

 

 

개념

재귀 호출

큰 수 연산

 

 

실행 결과

input = 3

input = 4

 

 

 

 

구현 코드(js)

/*
1914번 하노이 탑 자바스크립트 
https://www.acmicpc.net/problem/1914

오버플로우 해결 => BigInt
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/BigInt
*/

const fs = require('fs');
const input = fs.readFileSync(0).toString().trim().split('\n');
let n = Number(input[0]);
let resArr = [];

// 로컬 테스트용
// const filePath =
//   process.platform === 'linux' ? 'dev/stdin' : __dirname + '/input.txt';
// let n = fs.readFileSync(filePath).toString().trim().split('\n');
// n = Number(n[0]);

// 오버플로우 방지
console.log((2n ** BigInt(n) - 1n).toString());

const hanoi = (cnt, from, temp, to) => {
  if (cnt === 0) return;
  hanoi(cnt - 1, from, to, temp);
  resArr.push(from + ' ' + to);
  hanoi(cnt - 1, temp, from, to);
};

// disk 수가 20을 초과할 경우 무시
if (n > 20) return;
hanoi(n, 1, 2, 3);
console.log(resArr.join('\n'));

 

 

 

 

코드 설명

하노이 탑 자바스크립트 코드 찾기 힘들어서 그냥 제가 글 썼읍니다.. 🙃

 

 

 

먼저 하노이의 탑 문제를 정확히 이해했다면, 재귀함수를 사용해 간단하게 구현할 수 있다는 사실을 파악할 수 있습니다.

문제의 설명은 차치하고, 먼저 하노이 탑이 어떤 식으로 동작하는지 알아보기 위해 3개의 장대에 3개의 원반을 이동시킬 때 직접 탑을 쌓아보도록 합시다. 목표는 첫번째 장대에 있는 원반들처럼, 세번째 장대에 크기가 큰 순서부터 원반을 쌓아올리는 것입니다.

그렇다면 다음과 같이 동작할 것입니다!

 

출처: https://shoark7.github.io/programming/algorithm/tower-of-hanoi

 

이미 잘 정리되어 있는 그림이 있어서 가져와보았습니다.

크기가 작은 순서대로 원반 이름을 1, 2, 3이라고 붙인다고 하면, 초기에 원반 3에 위치한 원반 1, 2에 대해 무조건 첫번째가 아닌 다른 곳으로 잠시 옮겨놓아야 합니다. ( 네번째 그림을 참고하면 됩니다. )

그 이유는 뭘까요? 세번째 장대에 가장 크기가 큰 원반인 원반 3을 놓기 위해서는 그보다 크기가 작은, 즉 그 위에 있는 나머지 원반들을 모두 빼야하기 때문입니다. 그래야 원반 3을 첫번째 장대에서 세번째 장대로 이동할 수 있겠죠? 😀

 

만약 원반이 4개라면 어떨까? 과정과 최소 이동 횟수는 좀 달라질 수 있지만, 로직은 변하지 않아요!

즉, 크기가 가장 큰 원반 4를 제외하고 나머지 원반친구들 3개를 어딘가로 옮겨놓아야 한다. 무사히 옮겼다면 아까 원반이 3개였을 때처럼 똑같은 과정을 반복합니다. 입력값이 5, 6, 7.. 이렇게 늘어난다고 해도 가장 핵심적인 로직은 변하지 않을 것입니다.

 

출처: https://morm.tistory.com/104

 

여기서 우리는 변수 n을 설정할 수 있습니다. 이 변수는 원반의 개수이자 입력값 disk를 나타냅니다.

가장 아래에 있는 원반을 n이라고 하면, 우리는 그 위에 있는 1부터 n-1까지의 원반을 장대 1에서 장대 2로 옮깁니다. 그러면 원반 n을 장대 3으로 옮길 수 있습니다. 그다음 나머지를 하나씩 빼서 차곡 차곡 다시 그 위에 올리면 끝!

 

아래 코드는 이를 재귀함수로 구현한 함수 hanoi 입니다.

const hanoi = (cnt, from, temp, to) => {
  if (cnt === 0) return;
  hanoi(cnt - 1, from, to, temp);
  hanoi(cnt - 1, temp, from, to);
};

 

 

일반적으로 원판이 n개 일 때, 최소 이동 횟수 2^n -1번(메르센 수)의 이동으로 원판을 모두 옮길 수 있습니다.

 

재귀 함수 과정

1. cnt === 0에 도달하면 종료합니다. (cnt가 0이면 더 이상 이동할 원판이 없다는 뜻이므로.)
2. cnt - 1개의 원판을 from에서 temp로 이동합니다. (이때 to를 보조 기둥으로 사용)
3. 크기가 가장 큰 원판을 from에서 to로 이동합니다. 
4. cnt - 1개의 원판들을 temp에서 to로 이동합니다. (이때 from을 보조 기둥으로 사용)

여기서 보조 기둥은 크기 순서대로 올려야 하기 때문에 사용하는 장대라고 보시면 됩니다.

 

큰 수 연산 처리

하지만 여기서 문제가 끝나지 않습니다. 시간 및 메모리 제한을 위해서는 자바스크립트의 메모리 제한을 벗어나야 합니다.

재귀 함수의 경우 n의 크기가 커질수록 기하급수적으로 연산량이 늘어납니다. 자바스크립트의 숫자는 기본적으로 64비트 double까지의 값을 안전하게 표현할 수 있지만, 정수의 경우는 안전하게 표현할 수 있는 최대값이 2^53 - 1 입니다. 따라서 이 범위를 넘어가게 되면 정수 오버플로우가 발생하여 예상치 못한 값의 손실이 발생할 수 있습니다.

 

이를 해결하기 위해 mdn 공식 문서를 참고했습니다.

 

BigInt는 JavaScript에서 제공하는 데이터 타입으로, 아주 큰 정수를 안전하게 다룰 수 있도록 만들어졌습니다. BigInt를 사용하면 정수의 크기에 제한을 받지 않고, 큰 수를 정확하게 계산할 수 있습니다. 저는 메르센 수 공식을 사용하여 거듭 제곱 시 발생하는 정수 오버플로우를 해결하기 위해 다음과 같은 식을 사용했습니다.

 

console.log((2n ** BigInt(input) - 1n).toString());

 

• 2n은 BigInt로 2를 나타냅니다.  ** 연산자는 거듭제곱 연산자입니다. 
• 앞에서 빅인트로 변환했으므로, 1도 빅인트로 변환합니다.
• 큰 수로 변환된 이동 횟수 (2^n - 1)을 계산하고, .toString()을 통해 문자열 형태로 변환하여 출력합니다.

 

 

 

---