[백준 / JAVA] 1914번 하노이탑

이 글에는 백준 1914번 하노이탑 대한 풀이와 정답 코드(JAVA)가 있습니다.

문제

일반적인 하노이 탑 문제

원판의 개수(N)이 입력으로 주어진다 (1 ≤ N ≤ 100)

원판의 이동 횟수를 출력

N이 20 이하인 입력에 대해서는 수행 과정을 출력

 

풀이

• 하노이의 탑을 검색하면 나오는 위키 백과 설명입니다.

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.
1. 한 번에 한개의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 그렇기 때문에 프로그래밍 수업에서 알고리즘 예제로 많이 사용한다. 일반적으로 원판이 n개 일 때, 2n -1번의 이동으로 원판을 모두 옮길 수 있다(2n − 1는 메르센 수라고 부른다). 참고로 64개의 원판을 옮기는 데 약 18,446,744,073,709,551,615번을 움직여야 하고, 한번 옮길 때 시간을 1초로 가정했을 때 64개의 원판을 옮기는 데 5,849억 4,241만 7,355년이 걸린다.

• 하노이 탑은 재귀를 이용해서 풀이 하는 대표적인 문제이기 때문에 재귀를 사용하였습니다.
• 하노이 탑 원판의 이동 횟수 = 2 ^ N - 1 입니다.

 

• 주의 해야 할 점 : N의 최댓값으로 100이 주어 졌을 때, 2 ^ 100 -1 은 int, long 범위를 넘어가기 때문에 BigInteger를 사용해서 풀이해야 합니다.
  

  BigInteger count = new BigInteger("2");
  //주의!!) n이 100인 경우 long의 범위를 넘어간다
  System.out.println(count.pow(n).subtract(new BigInteger("1")));​

 

• 하노이의 탑의 3개 기둥을 왼쪽부터 1(from), 2(via), 3(to)이라고 할 때
  문제의 목적은 1(from) 기둥에서 3(to) 기둥으로 모든 원판을 옮기는 것이 핵심입니다.
  
  이 과정에서 N == 1이면 1(from)에서 바로 3(to)으로 가면 됩니다.
  

  

  if(n == 1) { //하나의 원판만 남았으면 1 -> 3
  	steps.add(new int[] {from, to});
  }​

  
  
  그렇지 않다면 N-1개의 원판(제일 큰 원판을 제외한)을 전부 통째로 들어서 1(from)에서 2(via)로 옮겨줍니다.
  
  그런후에는 제일 큰 원판이 1(from)에 남게 되므로 1(from)에서 3(to)으로 옮겨줍니다.
  
  그러면 제일 큰 원판이 3(to)에 가있기 때문에 아까 2에 옮겨놨던 N-1개의 원판들을 전부 통째로 들어서 2(via)에서 3(to)로 옮겨 줄 수 있습니다.
  

  

  
  

  else {
  	//1.N-1개의 원판을 1 -> 2
  	hanoi(n-1, from, via, to);
  	steps.add(new int[] {from, to});
  	//2.N-1개의 원판을 2 -> 3
  	hanoi(n-1, via, to, from);
  }​

 

전체 코드

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class BOJ_1914_하노이탑 {
    static ArrayList<int[]> steps;
    public static void main(String[] args) {
        Scanner scann = new Scanner(System.in);
        int n = scann.nextInt();

        steps = new ArrayList<int[]>();

        BigInteger count = new BigInteger("2");
        //주의!!) n이 100인 경우 long의 범위를 넘어간다
        System.out.println(count.pow(n).subtract(new BigInteger("1")));

        if(n <= 20) {
            hanoi(n, 1, 3, 2);

            for (int i = 0; i < steps.size(); i++) {
                int[] step = steps.get(i);
                System.out.println(step[0] + " " + step[1]);
            }
        }
    }

    private static void hanoi(int n, int from, int to, int via) {
        if(n == 1) { //하나의 원판만 남았으면 1 -> 3
            steps.add(new int[] {from, to});
        }else {
            //1.N-1개의 원판을 1 -> 2
            hanoi(n-1, from, via, to);
            steps.add(new int[] {from, to});
            //2.N-1개의 원판을 2 -> 3
            hanoi(n-1, via, to, from);
        }
    }

}

1914번: 하노이 탑

1914번: 하노이 탑