하노이탑

하노이 탑(Tower of Hanoi)은 수학적 퍼즐 게임으로, 세 개의 기둥과 여러 개의 서로 다른 크기의 원반으로 구성되어 있습니다. 이 게임의 목적은 한 기둥에 순서대로 쌓여 있는 원반들을 다른 기둥으로 옮기는 것인데, 이때 다음과 같은 규칙을 따라야 합니다:

 

• 한 번에 하나의 원반만 이동
  • 한 번에 한 개의 원반만 다른 기둥으로 옮길 수 있습니다.
• 큰 원반 위에 작은 원반을 놓을 수 없음
  • 원반이 다른 원반 위에 놓일 때, 그 아래에 있는 원반은 무조건 더 커야 합니다.

하노이 탑 알고리즘은 재귀적인 접근 방식을 사용하여 이 문제를 해결합니다.

가장 간단한 형태에서는, n개의 원반을 가지고 있을 때, 다음과 같은 단계를 거칩니다:

 

• 상위 n-1개의 원반을 '보조 기둥'으로 이동합니다.
• 가장 큰 원반을 '목표 기둥'으로 이동합니다.
• '보조 기둥'에 있는 n-1개의 원반을 '목표 기둥'으로 이동합니다.

이 알고리즘은 n의 값이 증가함에 따라 복잡도가 기하급수적으로 증가합니다. 예를 들어, 3개의 원반을 옮기는 데 필요한 최소 이동 횟수는 7회이지만, 4개의 원반을 옮기는 데는 15회, 5개는 31회가 필요합니다. 이동 횟수는 2^n - 1로 계산됩니다.

하노이 탑 문제는 재귀적 사고를 이해하고 연습하는 데 매우 유용하며, 컴퓨터 과학에서 알고리즘의 기본적인 예로 자주 사용됩니다.

 

---

 

자바로 구현

 

public class TowerOfHanoi {

    public static void main(String[] args) {
        // 원반의 개수를 설정합니다. 예를 들어 3으로 설정할 수 있습니다.
        int numberOfDisks = 3;
        // 원반을 'A' 기둥에서 'C' 기둥으로 'B' 기둥을 보조 기둥으로 사용하여 이동합니다.
        moveDisks(numberOfDisks, 'A', 'C', 'B');
    }

    // 원반을 이동시키는 메소드입니다.
    public static void moveDisks(int n, char fromPeg, char toPeg, char auxPeg) {
        // 기본 단계: 만약 원반의 수가 1이면, 바로 목표 기둥으로 이동합니다.
        if (n == 1) {
            System.out.println("원반 1을 " + fromPeg + "에서 " + toPeg + "로 이동");
            return;
        }

        // 재귀적 단계:
        // 1. 상위 n-1개의 원반을 보조 기둥으로 이동
        moveDisks(n - 1, fromPeg, auxPeg, toPeg);

        // 2. 남은 가장 큰 원반을 목표 기둥으로 이동
        System.out.println("원반 " + n + "을 " + fromPeg + "에서 " + toPeg + "로 이동");

        // 3. 보조 기둥에 있는 n-1개의 원반을 목표 기둥으로 이동
        moveDisks(n - 1, auxPeg, toPeg, fromPeg);
    }
}

 

이 코드는 각 원반의 이동을 콘솔에 출력합니다. moveDisks 메소드는 재귀적으로 호출되어 각 원반을 적절한 기둥으로 이동시킵니다. 원반의 수를 변경하려면 main 메소드에서 numberOfDisks 변수의 값을 수정하면 됩니다.