Chapter 05-3. 재귀 알고리즘_하노이의 탑

하노이의 탑(towers of Hanoi)

작은 원반이 위에, 큰 원반이 아래 위치하도록 쌓은 원반은 3개의 기둥 사이에서 옮기는 문제

원반은 1개씩만 옮길 수 있고 큰 원반에서 작은 원반 순으로 쌓으면서 최소 횟수로 옮겨야 함

 

하노이의 탑

package ch05_3;

import java.util.Scanner;

// 하노이의 탑
public class Ex01_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 scanner = new Scanner(System.in);

        System.out.println("하노이의 탑");
        System.out.print("원반의 개수: ");
        int n = scanner.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번 기둥으로 옮김
 */

 

메서드 recur3의 비재귀적 표현

package ch05_3;

import java.util.Scanner;

// 메서드 recur3의 비재귀적 표현
public class Ex02_recur3 {
    // 메서드 recur의 비재귀적 표현
    static void recur3(int n) {
        int[] nStk = new int[100];
        int[] sStk = new int[100];
        int ptr = -1;
        int sw = 0;
        
        while (true) {
            if (n > 0) {
                ptr++;
                nStk[ptr] = n;
                sStk[ptr] = sw;

                if (sw == 0) {
                    n = n - 1;
                } else if (sw == 1) {
                    n = n - 2;
                    sw = 0;
                }
                continue;
            }
            do {
                n = nStk[ptr];
                sw = sStk[ptr--] + 1;

                if (sw == 2) {
                    System.out.println(n);
                    if (ptr < 0) return;
                }
            } while (sw == 2);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("정수를 입력하세요: ");
        int x = scanner.nextInt();

        recur3(x);
    }
}
/*
정수를 입력하세요: 3
1
2
1
3
 */

 

하노이의 탑(기둥 이름을 문자열로 출력)

package ch05_3;

import java.util.Scanner;

// 하노이의 탑(기둥 이름을 문자열로 출력)
public class Ex03_hanoiEx {
    static String[] name = {"A 기둥", "B 기둥", "C 기둥"};
    // 원반을 x기둥에서 y기둥으로 옮김
    static void move(int no, int x, int y) {
        if (no > 1) {
            move(no - 1, x, 6 - x - y);
        }

        System.out.println("원반[" + no + "]을(를) " + name[x - 1] + "에서 " + name[y - 1] + "으로 옮김");

        if (no > 1) {
            move(no - 1, 6 - x - y, y);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

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

        move(n , 1, 3); // 1번 기둥에 쌓인 n개의 원반을 3번 기둥으로 옮김
    }
}
/*
하노이의 탑
원반의 개수: 3
원반[1]을(를) A 기둥에서 C 기둥으로 옮김
원반[2]을(를) A 기둥에서 B 기둥으로 옮김
원반[1]을(를) C 기둥에서 B 기둥으로 옮김
원반[3]을(를) A 기둥에서 C 기둥으로 옮김
원반[1]을(를) B 기둥에서 A 기둥으로 옮김
원반[2]을(를) B 기둥에서 C 기둥으로 옮김
원반[1]을(를) A 기둥에서 C 기둥으로 옮김
 */

 

하노이의 탑(비재귀적 구현)

package ch05_3;

import java.util.Scanner;

// 하노이의 탑(비재귀적 구현)
public class Ex04_hanoiN {
    // 원반을 x기둥에서 y기둥으로 이동
    static void move(int no, int x, int y) {
        int[] xStk = new int[100];
        int[] yStk = new int[100];
        int[] sStk = new int[100];
        int ptr = 0; // 스택 포인터
        int sw = 0;

        while (true) {
            if (sw == 0 && no > 1) {
                xStk[ptr] = x; // x 값 푸시
                yStk[ptr] = y; // y값 푸시
                sStk[ptr] = sw; // sw값 푸시
                ptr++;
                no -= 1;
                y = 6 - x - y;
                continue;
            }

            System.out.printf("원반[%d]을 %d 기둥에서 %d 기둥으로 이동\\n", no, x, y);

            if (sw == 1 && no > 1) {
                xStk[ptr] = x;
                yStk[ptr] = y;
                sStk[ptr] = sw;
                ptr++;
                no -= 1;
                x = 6 - x - y;
                if(++sw == 2) sw = 0;
                continue;
            }

            do {
                if (ptr-- == 0) return; // 스택이 비어 있으면
                x = xStk[ptr]; // 값을 저장하고 있는 x를 팝
                y = yStk[ptr]; // 값을 저장하고 있는 y를 팝
                sw = sStk[ptr] + 1; // 값을 저장하고 있는 sw을 팝
                no++;
            } while (sw == 2);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("하노이의 탑");
        System.out.print("원반의 개수: ");
        int n = scanner.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 기둥으로 이동
 */