[자료 구조와 알고리즘] 재귀 - 하노이 탑

 

 

 

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘

 

재귀 - 하노이 탑

 

 

 

 

📍 하노이 탑

👉🏻 세 개의 기둥과 서로 다른 크기의 원반들이 있음

👉🏻 가장 큰 원반이 아래 있고, 위로 갈수록 작은 원반으로 이루어짐

 

👉🏻 다른 기둥으로 원반을 옮겨야 하는데

규칙 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