🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
재귀 - 하노이 탑
📍 하노이 탑
👉🏻 세 개의 기둥과 서로 다른 크기의 원반들이 있음
👉🏻 가장 큰 원반이 아래 있고, 위로 갈수록 작은 원반으로 이루어짐
👉🏻 다른 기둥으로 원반을 옮겨야 하는데
규칙 1) 한 번에 하나의 원반만 움직일 수 있음규칙 2) 가장 위에 있는 원반만 움직일 수 있음규칙 3) 아래에 작은 원반이 올 수 없음
👉🏻 즉, 기둥 B는 기둥 A의 원반을 기둥 C로 옮기기 위해 임시로 거쳐가는 곳
📍 하노이 탑을 하향식 재귀 방식으로 생각하면?
👉🏻 가장 큰 크기의 원반 3을 가장 아래에 옮겨야 하기 때문에 첫 번째 목표는 원반 3을 기둥 C로 이동시켜야 함
👉🏻 즉 원반 1, 2를 기둥 B로 옮기는 것을 하위 문제로 생각함
👉🏻 👉🏻 원반 1, 2를 기둥 B로 옮기기 위해서는 원반 1을 기둥 C로 옮겨야 함
👉🏻 👉🏻 👉🏻 원반 1을 기둥 C로 옮기기 위해서는 바로 기둥 C로 이동시킬 수 있음 (더 이상 하위 문제 없음)
👉🏻 👉🏻 👉🏻 👉🏻 기둥 B의 원반 1, 2를 기둥 C로 옮기기 위해서는, 원반 2를 기둥 C로 옮겨야 함
👉🏻👉🏻 👉🏻 👉🏻 👉🏻 원반 2를 기둥 C로 옮기기 위해서는 원반 1을 먼저 기둥 A로 옮겨야 함
📍 하노이 탑 코드
[ hanoi.mjs ]
function hanoi(count, from, to, temp) {
// 기둥 A에 원반 3개가 꽂혀 있다고 생각하고 코드 작성 중
// 최종 목표: 원반 세 개를 A에서 C로 옮겨야 함
if(count == 0) return; // 기저 조건: 원반 없을 때 함수 종료
// 원반 1, 2가 기둥 B에 위치해야 원반 3이 기둥 C로 이동 가능!
// 2, A, B, C
hanoi(count - 1, from, temp, to);// 원반 1, 2가 기둥 A에서 시작해 B로 이동하는 데 C를 임시로 사용함
console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`);
// 2, B, C, A
hanoi(count - 1, temp, to, from);
}
hanoi(3, "A", "C", "B");
// 원반 개수, from, to, temp