[Java] 백준 1914번 : 하노이 탑

1. 문제

 

하노이의 탑 문제이다. 옮긴 횟수와 n<=20 일 때는 과정까지 출력하는 문제이다. 

 

2. 하노이의 탑

출처 : 위키백과 https://ko.wikipedia.org/wiki/하노이의_탑

 

하노이의 탑은 퍼즐의 일종이다. 세 기둥과 여러개의 원판이 있고 원판은 한 기둥에 순서대로 쌓여있다. 하노이의 탑은 규칙 3가지를 지키면서 한 기둥에 있는 원판들을 다른 기둥에 순서 그대로 옮겨야한다.

 

• 더 작은 원판 위에 더 큰 원판을 올릴 수 없다.
• 가장 위에 있는 원판만 옮길 수 있다.
• 한 번에 한 개의 원판만 옮길 수 있다.

 

하노이의 탑 문제는 재귀 함수를 이용해서 풀 수  있는 가장 유명한 예제 중 하나라고 한다.

한 기둥의 n장의 원판을 다른 기둥으로 옮기기 위한 최소 횟수는 2^n - 1 이다.

 

하노이 타워에 대한 프랑스 수학자 Edouard Lucas 가 만든 유래도 있으니 찾아보길 바란다.

 

3. 풀이

앞서 말했듯이 하노이 탑 문제는 재귀 함수를 이용해서 풀 수 있다. n개의 원판을 옮기기 위한 최소 횟수는 2^n - 1이며, 

이동 순서는 항상 재귀적으로 동일한 패턴을 따른다.

• n-1개의 원판을 두 번째 기둥으로 옮김
• n번째 원판을 세 번째 기둥으로 옮김
• n-1개의 원판을 세 번째 기둥으로 옮김

 

두 번째 기둥으로 옮길 때, 보조기둥으로 사용하는 기둥은 세 번째 기둥이다. 마찬가지로 세 번째 기둥으로 옮길 때에는 첫 번째 기둥이 보조기둥이 된다. 이 과정을 모두 반복하여 과정을 구하는 함수를 만들고 출력하면 된다. 매우 큰 수가 출력될 것이기 때문에 자바의 BigInteger을 사용해야한다.

 

4. 코드

Java 코드

 

import java.util.*;
import java.math.*;

class Main {
	// 원판을 옮기는 과정을 출력하는 함수
    static void hanoi(int n, int from, int to, int aux){
        if(n==1) {
            System.out.println(from + " " + to);
            return;
        }
        else{
            hanoi(n-1, from, aux, to);
            System.out.println(from + " " + to);
            hanoi(n-1, aux, to, from);
        }
    }
        
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        BigInteger result = BigInteger.TWO.pow(n).subtract(BigInteger.ONE);
        System.out.println(result);
        
        if(n<=20){
            hanoi(n, 1, 3, 2);
        }
        return;
    }
}

 

BigInteger.TWO.pow(n).subtract(BigInteger.ONE);는 2^n - 1을 의미한다. n이 20 이하일 경우 hanoi 함수를 실행한다. (원판 개수, 시작할 기둥, 최종적으로 옮길 기둥, 보조 기둥). n==1일 경우 시작 기둥과 최종 기둥만 출력하고 리턴한다.

 

1이 아닐 때의 하노이 함수의 로직을 보자.

n-1개의 원판을 첫 번째 기둥(시작)에서 두 번째 기둥(최종)으로 옮길 때 세 번째 기둥이 보조 기둥으로 쓰인다.

시작 기둥의 n번째 원판을 최종 기둥으로 옮기는 과정을 출력한다.

n-1개의 원판을 두 번째 기둥(시작)에서 세 번째 기둥(최종)으로 옮길 때 첫 번째 기둥이 보조 기둥으로 쓰인다.

 

 

감사합니다 （*＾-＾*）