하노이 탑 - Java의 알고리즘 및 구현

하노이 탑은 프로그래밍 세계에서 고전적인 문제입니다. 문제 설정은 3개의 막대/페그와 n개의 디스크로 구성됩니다.

디스크는 한 페그에서 다른 페그로 이동할 수 있습니다. n개의 디스크는 크기가 다릅니다.

처음에는 모든 디스크가 첫 번째 타워에 쌓입니다. 디스크는 디스크가 항상 자체보다 큰 디스크 위에 있는 방식으로 쌓입니다.

하노이 탑 기본 설정

재미있는 사실 : 이 게임은 19세기 프랑스 수학자 Édouard Lucas가 발명했습니다. 그것은 퍼즐이 어린 사제들의 정신 훈련을 향상시키기 위해 사용되었다고 추정되는 힌두교 사원의 전설과 관련이 있습니다.

문제 설명

Move all the disks stacked on the first tower over to the last tower using a helper tower in the middle. While moving the disks, certain rules must be followed. These are : 

1. Only one disk can be moved.

2. A larger disk can not be placed on a smaller disk.

따라서 첫 번째 타워에서 마지막 타워로 모든 디스크를 이동해야 합니다. 한 번에 하나의 디스크만 이동할 수 있으며 큰 디스크 위에 작은 디스크를 놓지 마십시오.

이렇게 하려면 도우미/보조 타워라고 하는 추가 타워가 있습니다.

한 번에 하나의 디스크만 이동할 수 있으므로 이동하는 디스크는 탑의 맨 위에 있어야 합니다.

하노이 탑 문제에 대한 이론적 해결책

타워의 이름을 A,B,C로 지정하고 디스크의 이름을 1,2,3으로 지정하겠습니다.

간단한 재귀를 사용하여 이 문제를 해결합니다. 3개의 디스크를 최종 타워로 가져오려면 다음을 수행해야 합니다.

디스크 번호 1과 2를 타워 B로 가져갑니다.
3번 디스크를 타워 C로 이동합니다.
디스크 번호 1과 2를 B에서 C로 가져옵니다.

물론 제약 때문에 이렇게 할 수는 없습니다. 그러나 이것을 재귀적으로 수행하는 함수를 만드는 데 사용할 수 있습니다.

우리가 작성하는 함수에서 디스크의 움직임을 인쇄합니다.

Java로 하노이 타워 솔루션 구현

하노이 탑 문제를 해결하기 위한 코드의 두 가지 주요 부분을 이해하는 것부터 시작하겠습니다.

1. 기본 사례

코드의 기본 사례는 디스크가 하나만 있는 경우입니다. 즉 n=1입니다.

 if (n == 1)
        {
            System.out.println("Take disk 1 from rod " +  from_rod + " to rod " + to_rod);
            return;
        }

2. 재귀 호출

하노이 탑을 해결하기 위한 재귀 호출은 다음과 같습니다.

 towerOfHanoi(n-1, from_rod, helper_rod, to_rod);
        System.out.println("Take disk " + n + " from rod " +  from_rod + " to rod " + to_rod);
        towerOfHanoi(n-1, helper_rod, to_rod, from_rod);
    }

이들은 다음과 동일합니다.

상단 n-1 디스크를 보조 타워로 이동합니다.
원본 막대에서 대상 막대로 디스크 1개를 이동합니다.
보조 디스크에서 대상 로드로 n-1 디스크를 가져옵니다.

하노이 탑의 완벽한 Java 구현

package com.JournalDev;
public class Main {
    static void towerOfHanoi(int n, char from_rod, char to_rod, char helper_rod)
    {
        if (n == 1)
        {
            System.out.println("Take disk 1 from rod " +  from_rod + " to rod " + to_rod);
            return;
        }
        towerOfHanoi(n-1, from_rod, helper_rod, to_rod);
        System.out.println("Take disk " + n + " from rod " +  from_rod + " to rod " + to_rod);
        towerOfHanoi(n-1, helper_rod, to_rod, from_rod);
    }

    public static void main(String args[])
    {
        int n = 5;
        towerOfHanoi(n,'A','C', 'B');
    }

}

코드의 출력은 다음과 같습니다.

Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 3 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C

다음 그림을 사용하여 프로세스를 이해할 수 있습니다. 원하는 수의 디스크에 대해 코드를 실행할 수 있습니다.

n=5에 대한 출력은 다음과 같습니다.

Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 3 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 4 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 2 from rod C to rod A
Take disk 1 from rod B to rod A
Take disk 3 from rod C to rod B
Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 5 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 3 from rod B to rod A
Take disk 1 from rod C to rod B
Take disk 2 from rod C to rod A
Take disk 1 from rod B to rod A
Take disk 4 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 3 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C

n개의 디스크에 대한 단계 수를 계산하는 공식은 다음과 같습니다.

(2^n)-1

결론

이것이 재귀를 사용하여 하노이 탑을 푸는 방법입니다. 저희와 함께 즐거운 학습이 되셨기를 바랍니다!