하노이탑 알고리즘 Java 샘플

재귀호출 알고리즘중 대표격인 하노이탑 알고리즘에 대한 Java 샘플입니다.
하노이탑에 대한 설명은 워낙 많기 때문에 아래 링크로 대체합니다.

하노이탑 - 위키백과

문제 풀이 방식

다양한 원리와 방식에 대한 설명들이 많은데 저는 다음과 같이 단순히 생각해보았습니다.

위와 같은 하노이탑중 4번 블럭을 3번째 위치로 옮기기 위해서는 아래와 같이 1,2,3번블럭을 모두 2번째 위치로 옮겨두면 가능합니다.

그리고 위 그림처럼 3번 블럭을 2번째 위치로 옮기기 위해서는 1,2,번블럭을 아래와 같이 3번 위치에 옮기면 됩니다.

위와 같이 하나의 블럭을 옮기기 위한 원리는 “해당 블럭 위에 있는 블럭을 임시 위치에 두고 해당 블럭을 옮긴다”가 되며 그 원리를 구현한 소스는 아래와 같습니다.

public static void move(Integer target, Stack<Integer> srcStack, Stack<Integer> destStack, Stack<Integer> bufferStack)
{
    if (target == 1)
    {
        moveBlock(srcStack, destStack);
        return;
    }

    move(target-1, srcStack, bufferStack, destStack);
    moveBlock(srcStack, destStack);
    move(target-1, bufferStack, destStack, srcStack);
}

private static void moveBlock(Stack<Integer> srcStack, Stack<Integer> destStack)
{
    destStack.push(srcStack.pop());
}

위 로직을 실행하면 아래와 같이 동작하게 됩니다.

전체소스 경로 : (https://github.com/jistol/sample-algorithm/tree/master/hanoi)[https://github.com/jistol/sample-algorithm/tree/master/hanoi]