하노이의 탑

하노이의 탑이란? 작은 원반이 위에, 큰 원반이 아래에 위치하도록 쌓은 원반을 3개의 기둥 사이에서 옮기는 문제이다. 모든 원반은 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여있다. 이 상태에서 모든 원반을 세번째 기동으로 최소의 횟수로 옮기면 되는 것이다. 원반은 1개씩만 옮길 수 있고, 큰 원반을 작은 원반 위에 쌓을수는 없다.

위 그림에서 시작 기둥에 있는 원판(색칠된)들을 중간 기둥을 활용하여 목표 기둥으로 옮기면 되는 게임이다. 어렸을 때이런 장난감이 유치원에 있었던걸로 기억한다.

위처럼 원판이 3개인 경우는 아래의 과정을 거친다.

1. 빨간원판을 1번기둥에서 3번기둥으로 옮긴다.
2. 노란원판을 1번기둥에서 2번기둥으로 옮긴다.
3. 빨간원판을 3번기둥에서 2번기둥으로 옮긴다.
4. 파란원판을 1번기둥에서 3번기둥으로 옮긴다.
5. 빨간원판을 2번기둥에서 1빈기둥으로 옮긴다.
6. 노란원판을 2번기둥에서 3번기둥으로 옮긴다.
7. 빨간원판을 1번기둥에서 3번기둥으로 옮긴다.

위와 같은 과정을 거쳐서 목표 기둥인 3번기둥으로 파-노-빨 순서대로 쌓여있게 된다.
이를 코드로 아래처럼 구현이 가능하다.

package 알고리즘.재귀알고리즘;

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.printf("원반[%d]을(를) %d번 기둥에서 %d번 기둥으로 옮김\n", 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,2,3으로 나타내기에 기둥 번호의 합이 6이다. 시작 기둥, 목표기둥이 어느 기둥이더라도 중간 기둥은 6-x-y로 구할 수 있게 된다. move메서드는 no개의 원반을 다음과 같이 3단계를 거쳐 옮긴다.

1. 바닥의 원반을 제외한 그룹(원반[1]~원반[no-1])을 시작 기둥에서 중간 기둥으로 옮긴다.
2. 바닥의 원반 no를 시작 기둥에서 목표 기둥으로 옮겼음을 출력한다.
3. 바닥의 원반을 제외한 그룹(원반[1]~원반[no-1])을 중간 기둥에서 목표 기둥으로 옮긴다.

물론 1,3의 실행은 no가 1보다 큰 경우이므로 no가 1인 부분(최하위에 해당하는 부분)에서는 2만 실행된다.