[JAVA] 재귀 알고리즘: 하노이의 탑

🔮 하노이의 탑

하노이의 탑은 시작 기둥에 있는 원반들을 목표 기둥(제일 마지막에 있는 기둥)으로 최소의 횟수로 이동시키는 것입니다.

1. 원반 1을 첫 번째 기둥에서 세 번째 기둥으로 옮긴다.
2. 원반 2를 첫 번째 기둥에서 두 번째 기둥으로 옮긴다.
3. 원반 1을 세 번째 기둥에서 두 번째 기둥으로 옮긴다.
4. 원반 3을 첫 번재 기둥에서 세 번째 기둥으로 옮긴다.
5. 원반 1을 두 번째 기둥에서 첫 번째 기둥으로 옮긴다.
6. 원반 2를 두 번째 기둥에서 세 번째 기둥으로 옮긴다.
7. 원반 1을 첫 번째 기둥에서 세 번째 기둥으로 옮긴다.

📍 일반화

가장 큰 원반을 세 번째 기둥으로 옮기는 것을 목표로 할 때

1. 가장 큰 원반 외의 나머지 원반들을 하나의 그룹으로 묶어서 두 번째 기둥으로 보낸다.
2. 가장 큰 원반을 세 번째 기둥으로 보낸다.
3. 두 번째 기둥에 있는 그룹을 세 번째 기둥으로 옮긴다.
   

import java.util.Scanner;

public class Hanoi {
    // no개의 원반들 x번 기둥에서 y번 기둥으로 옮김.
    static void move(int no, int x, int y) {
        if (no > 1)
            move(no - 1, x, 6 - x - y);

        System.out.println("원반[" + no + "]을 " + x + "기둥에서 " + y + "기둥으로 옮김");

        if (no > 1) {
            move(no - 1, 6 - x - y, y);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("하노이의 탑");
        System.out.print("원반 개수 : ");
        int n = sc.nextInt();

        move(n, 1, 3); // 1번의 기둥의 n개의 원반들 3번의 기둥으로 옮김.
    }
}

📌 1번 원반이 가장 큰 원반

각 이모티콘의 의미 : 그 함수에서 move가 2번 불러짐. 💥는 마지막 함수라는 의미

1. 🍹move(3, 1, 3) : 3번 원반을 첫 번째 기둥에서 세 번째 기둥으로 옮겨 -> 4️⃣
2. 🍹, 🍺move(2, 1, 2) : 2번 원반을 첫 번째 기둥에서 두 번째 기둥으로 옮겨 -> 2️⃣
3. 💥move(1, 1, 3) : 1번 원반을 첫 번째 기둥에서 세 번째 기둥으로 옮겨 -> 1️⃣
4. 🍺, 💥move(1, 3, 2) : 1번 원반을 세 번째 기둥에서 두 번째 기둥으로 옮겨 -> 3️⃣
5. 🍹, 📗move(2, 2, 3) : 2번 원반을 두 번째 기둥에서 세 번째 기둥으로 옮겨 -> 6️⃣
6. 💥move(1, 2, 1) : 1번 원반을 두 번째 기둥에서 첫 번째 기둥으로 옮겨 -> 5️⃣
7. 📗, 💥move(1, 1, 3) : 1번 원반을 첫 번째 기둥에서 세 번째 기둥으로 옮겨 -> 7️⃣

1️⃣ 2️⃣ 3️⃣ : 하나의 함수가 끝나면 한 그룹이 중간기둥으로 옮겨져 있다.
4️⃣ : 바닥 원반을 시작 기둥에서 목표 기둥으로 옮긴다.
5️⃣ 6️⃣ 7️⃣ : 중간 기둥에서 목표 기둥으로 옮긴다.

• 재귀 함수이므로 함수의 조건이 성립을 한다면 실행되지 않고 다시 move 함수로 이동하므로 코드 진행 순서와 실행 순서는 다를 수 있다.

❓ 근데 왜 정확히 6 - x - y인지는 모르겠다. 무슨 규칙이 있어서 6이라는 숫자를 쓴 것 같은데 이 숫자가 어떻게 도출되었는지는 모르겠음.