하노이탑 알고리즘 이해하기 (재귀함수 사용)

 

 

 

 

장대 위에 n개의 원판이 있는 경우

크게 총 3단계로 이루어짐!

 

1. n-1개의 원판을 2번 장대(중간 장대)로 이동시킨다.

2. 가장 밑에 있던 n번째 원판을 3번 장대(목표 장대)로 이동시킨다.

 

3. 2번 장대의 n-1개의 원판을 3번 장대(목표 장대)로 이동시킨다. 

 

 

 private static void hanoi(int n, int start, int mid, int end) {
        if (n == 1) { //남아있는 원판이 1개인 경우
            System.out.println(start + " " + end);
            return;
        }
        hanoi(n - 1, start, end, mid); //원판을 중간 장대로 이동
        System.out.println(start + " " + end);
        hanoi(n - 1, mid, start, end); //원판을 기존 목표 장대로 이동
    }

 

하노이 재귀함수 작성

 

 

원판이 2개일 때 -> 3회

원판이 3개일 떄 -> 7회

원판이 4개일 때 -> 15회

n개의 원판을 3번 장대로 옮길 때 최소 횟수 = 2^n -1 의 일반항을 얻을 수 있음

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int answer = (int) (Math.pow(2, N) - 1);
        System.out.println(answer);
        hanoi(N, 1, 2, 3);


    }

    private static void hanoi(int n, int start, int mid, int end) {
        if (n == 1) {
            System.out.println(start + " " + end);
            return;
        }
        hanoi(n - 1, start, end, mid);
        System.out.println(start + " " + end);
        hanoi(n - 1, mid, start, end);

    }
}

 

 

 

실패 ㅜㅜ

 

구글링 해보니 n의 범위를 지정해주어야 하고,

n<=20인 경우에도 값이 기하급수적으로 증가하기 때문에 bigInteger로 처리해주어야 한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        BigInteger count = new BigInteger("2");
        System.out.println(count.pow(N).subtract(new BigInteger("1")));
        if (N <= 20) {
            hanoi(N, 1, 2, 3);
        }
    }

    private static void hanoi(int n, int start, int mid, int end) {
        if (n == 1) {
            System.out.println(start + " " + end);
            return;
        }
        hanoi(n - 1, start, end, mid);
        System.out.println(start + " " + end);
        hanoi(n - 1, mid, start, end);

    }
}

성공 !!