[재귀/BigInteger] 1914번 하노이탑

재귀를 연습하기 좋은 문제.

하노이 탑은 유명한 재귀 호출 문제이다.

규칙은 다음과 같다

기둥이 3개가 있는데 1번 기둥에 1,2,3번 원판이 꽂혀있다. 1<2<3순서대로 크기가 크다. 이 상황에서 1번 기둥에 있는 모든 원판을 3번 기둥으로 옮겨야 하는데, 옮기는 중간 중간에 무조건 작은 원판이 큰 원판 위에 있어야 한다.

단한번이라도 큰 원판밑에 작은 원판이 깔리는 일이 없어야 한다.

이 규칙을 지키면서 1번 -> 3번 기둥으로 모든 원판을 옮기기 위해서는 다음과 같이 옮겨야 한다.

1. 1번 기둥(시작기둥)에 있는 원판중 n-1개를 2번 기둥(중간기둥)으로 옮긴다

2. 1번 기둥에 남아있는1개의 가장 큰 원판을 3번 기둥(도착기둥)으로 옮겨 준다.

3. 아까 1번에서 옮겨놨던 2번 기둥(중간 기둥)에 있던 n-1개의 원판을 다시 3번 기둥으로 옮겨준다.

이런 과정이 계속해서 반복 된다.

이것을 알고리즘으로 풀기 위해서는 재귀 호출을 해야한다.

다시말해서 1번 기둥에서 2번기둥을 거쳐 3번 기둥으로 옮기는 일은

1. 시작 기둥에 꽂힌 n-1개의 원판을 중간 기둥으로.

2. 시작 기둥에 꽂힌 마지막 1개의 원판을 도착 기둥으로

3. 중간 기둥으로 옮겨놨던 n-1개의 원판을 다시 도착 기둥으로 옮긴다.

위의 3가지 과정이 하노이 탑의 핵심이다.

코드로 표현하면 다음과 같다.

    static void hanoi(int n, int start, int mid, int end) { 
        //n : 원판의개수, start : 시작막대번호 mid : 징검다리 막대 번호 end : 도착지막대번호
        if (n == 1) {
            System.out.println(start+" "+end);
            return;
        }
 
        //n개의 원판을 시작지에서 도착지로 옮기는 과정을 아래의 3가지 과정으로
        //쪼갤수 있음.
        hanoi(n - 1, start, end, mid); 
        //1번과정 : n-1개 원판을 시작막대에서 도착 막대를 거쳐 중간막대로
        System.out.println(start+" "+end);
        //2번과정 : 시작막대의 마지막 남은 1개 원판을 도착지 막대로
        hanoi(n - 1, mid, start, end);
        //3번과정 : 중간막대로 옮겼던 n-1개 원판을 다시 도착지 막대로 이동.
        return;
    }

하노이 타워의 원판 이동 횟수는 2^n -1 이라고 하는데, 이것은 어렵기도하고 필요없을거 같아서 그냥 받아들이기로 했다.

이 문제에서 중요한것은 재귀 호출이지 수학적인 계산이 아니기 때문이다.

또한 이 문제에서 n이 100까지 입력으로 주어진다. 그렇게 될 경우 원판의 이동 횟수가 2^100-1이라는 엄청난 횟수가 생긴다. c++에서는 8byte까지 밖에 표현이 불가능하다 이말은 2^64 정도의 크기의 정수만 표현이 가능하다는 의미이다.

저런 엄청난 숫자는 일반적인 자료형으로 표현이 불가능 하다.

c++로 빅 인티져를 구현하는것이 약간 이해가 안되서 그냥 자바에 있는 빅 인티저를 갖다 쓰기로 했다.

big integer를 사용하게 되면 무한대의 숫자도 표현이 가능하다고 한다.

 
import java.math.*;
import java.util.Scanner;
public class Main {
    
    static void hanoi(int n, int start, int mid, int end) { 
        //n : 원판의개수, start : 시작막대번호 mid : 징검다리 막대 번호 end : 도착지막대번호
        if (n == 1) {
            System.out.println(start+" "+end);
            return;
        }
 
        //n개의 원판을 시작지에서 도착지로 옮기는 과정을 아래의 3가지 과정으로
        //쪼갤수 있음.
        hanoi(n - 1, start, end, mid); 
        //1번과정 : n-1개 원판을 시작막대에서 도착 막대를 거쳐 중간막대로
        System.out.println(start+" "+end);
        //2번과정 : 시작막대의 마지막 남은 1개 원판을 도착지 막대로
        hanoi(n - 1, mid, start, end);
        //3번과정 : 중간막대로 옮겼던 n-1개 원판을 다시 도착지 막대로 이동.
        return;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        BigInteger bi = new BigInteger("2");
        BigInteger c = bi.pow(n).subtract(BigInteger.ONE);
        System.out.println(c);
        if (n <= 20)
            hanoi(n, 1, 2, 3);
        
    }
 
}