[JAVA] 하노이의 탑 (Tower of Hanoi)

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

---

하노이의 탑 설명

1, 2, 3번 기둥 이렇게 3개의 기둥과 크기가 모두 다른 n개의 원판이 있을 때, n개의 원판 모두 1번 기둥에 크기가 큰 원판순으로 아래에 위치되어 있다. 이러한 기둥들을 3번 기둥에 모두 옮겨야 하는데, 한 번에 한 원판만 옮길 수 있고 크기가 작은 원판 위에 크기가 큰 원판을 올릴 수 없다.

이러한 원판 이동을 최소한의 횟수로 옮기는 것이 하노이의 탑의 규칙이다.

https://brunch.co.kr/@younggiseo/139

 

하노이의 탑 풀이

가장 위에 있는 원반을 1번원반, 그 아래의 원반을 2번 원반, 가장 아래에 있는 원반을 n번 원반이라고 하면

디테일한 과정 말고 큰 과정을 나열하면 3가지로 압축할 수 있다.

• 1 ~ n-1번 원반을 2번 기둥에 옮긴다.
• n번 원반을 3번 기둥에 옮긴다.
• 1 ~ n-1번 원반을 3번 기둥에 옮긴다.

https://m.blog.naver.com/PostView.nhn?blogId=puri8467&logNo=221440092130&proxyReferer=https:%2F%2Fwww.google.com%2F

 

구현

재귀 알고리즘으로 하노이의 탑 문제를 구현하는 것은 간단하다.

다만 이해하는 것은 개인적으로 조금 힘들었다.

import java.util.Scanner;

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 stdIn = new Scanner(System.in);

        System.out.println("하노이의 탑");
        System.out.print("원반의 개수 : ");
        int n = stdIn.nextInt();

        move(n, 1, 3);    // 제 1 기둥에 쌓인 n개를 제 3 기둥으로 옮김
    }
}
/*
원반 개수：3
원반[1]을 1번 기둥에서 3기둥으로 옮김
원반[2]을 1번 기둥에서 2기둥으로 옮김
원반[1]을 3번 기둥에서 2기둥으로 옮김
원반[3]을 1번 기둥에서 3기둥으로 옮김
원반[1]을 2번 기둥에서 1기둥으로 옮김
원반[2]을 2번 기둥에서 3기둥으로 옮김
원반[1]을 1번 기둥에서 3기둥으로 옮김
*/

이 알고리즘은 기둥 번호를 정수 1, 2, 3으로 나타낸다.

기둥 번호의 합이 6이므로 시작 기둥, 목표 기둥이 어느 기둥이더라도 중간 기둥은 6 - x - y로 구할 수 있다.

move 메서드는 no개의 원반을 아래와 같이 3단계를 거쳐 옮긴다.

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

 

 

아래의 코드는 개인적으로 이 메소드의 실행 과정을 이해하기 위해 덧붙인 코드이다.

static void hanoi(int TopNum, int x, int y) {
    if (TopNum > 1) //첫 번째 조건문
    {
        System.out.println("------------------------------");
        System.out.println("TopNum = " + TopNum);
        System.out.println("첫 번째 조건문 실행");
        System.out.print(TopNum - 1 +" ");
        System.out.print(x + " ");
        System.out.println(6-x-y);
        System.out.println("------------------------------");
        hanoi(TopNum - 1, x, 6 - x - y);
    }
    System.out.println("원반[" + TopNum + "]을 " + x + "기둥에서 " + y + "기둥으로 옮김, TopNum = " + TopNum );

    if (TopNum > 1) //두 번째 조건문
    {
        System.out.println("------------------------------");
        System.out.println("TopNum = " + TopNum);
        System.out.println("두 번째 조건문 실행");
        System.out.print(TopNum - 1 +" ");
        System.out.print(6 - x - y + " ");
        System.out.println(y);
        System.out.println("------------------------------");
        hanoi(TopNum - 1, 6 - x - y, y);
    }
}

 

최소 움직임 수

하노이의 탑 문제를 해결하기 위한 최소 움직임 수는 2ⁿ-1이다.

즉 원반이 3개이면 최소 움직임 수는 8-1 = 7이다. 위 메소드에서 hanoi(3)의 결과와 같다.

원반이 4개라면 16 -1 = 15이다.

 

추가적으로 원반이 4개라면, 1~3번의 원반을 2번 기둥에 옮기고, 4번 원반을 3번 기둥에 옮기고 다시 1~3번의 원반을 3번 기둥에 옮기면 된다.

즉, 제일 아래의 원반 번호 n을 제외한 n-1개의 원반을 2번 기둥에 옮기고,  원반 번호 n을 3번 기둥으로 옮기고, n-1개의 원반을 다시 3번 기둥에 옮기는 것과 같다.

hanoi(3) + 1 + hanoi(3)과의 움직임 수가 같다.

이를 일반화하면 아래와 같다.

• hanoi(n) = 2 * hanoi(n-1)