백준 1914번: 하노이 탑(java)

문제

https://www.acmicpc.net/problem/1914

1914번: 하노이 탑

난이도: 실버1

유형 :재귀

 

접근법

 

좌측의 기둥부터 1, 2, 3이라 가정했을때 아래의 조건을 만족 하면서 1->3 으로 모든 원판을 옮기는 것 이다.

"큰 원판이 작은 원판 위에 있어서는 안 된다"
"한 번에 한개의 원판만 움직일 수 있다."

 

원판이 N개 일때 하노이 탑 원판의 이동 횟수는 2^N-1 가 된다. 

N의 최댓값으로 100이 주어 지면 2^100 -1 은 int, long 범위를 초과하기 때문에 BigInteger 를 사용해야 한다.

 

하노이탑 풀이 과정을 일반화 한다면 아래와 같은 과정을 거친다.

1. 마지막 원반을 제외한 원반을 중간 장대로 옮긴다. (1번 기둥 n-1 개를 -> 2번 기둥으로 옮긴다.)
2. 마지막 원반을 마지막 장대로 옮긴다. (1번 기둥에 남은 마지막 원판을 3번 기둥에 옮긴다.)
3. 나머지 원반을 중간 장대에서 목표 장대로 옮긴다. (2번 기둥의 n-1개 원판 ->3번 기둥으로 옮긴다.)

이 과정을 반복 한다.

 

의사코드 형태로 옮기자면 이와같다.

hanoi_func(원반의 갯수, 시작, 중간, 목표 ){
   if(옮길 원반이 1개면){
        print(start+ " " + end);
        return;
    }

    hanoi_func(N-1, 시작, 목표, 중간); //n-1개의 원판을 시작막대에서 도착 막대를 거쳐 중간 막대로
    print((start + " " + end); // 시작막대의 마지막 남은 1개 원판을 도착지 막대로
    hanoi_func(N-1, 중간, 시작, 목표);  // 중간막대로 옮겻던 N-1개의 원판들을 도착지 막대로 이동.
    return;
}

 

풀이

import java.io.*;
import java.math.BigInteger;

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        BigInteger bi = new BigInteger("2");
        BigInteger c = bi.pow(N).subtract(BigInteger.ONE); // 2^N -1
        System.out.println(c);
        if(N<=20){
            hanoi(N,1,2,3);
        }
        System.out.println(sb);
    }

    static void hanoi(int N, int from , int by, int to) {

        if (N == 1) {
            sb.append(from + " " + to + "\n");
            return;
        }else {
            hanoi(N-1, from, to, by);
            sb.append(from + " "+ to + "\n");
            hanoi(N-1, by, from, to);
        }
    }
}