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

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

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

1914번: 하노이 탑

[정답 코드]

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N = 0;

    public static void main(String[] args) throws Exception {

        // 원판의 개수 입력
        N = Integer.parseInt(br.readLine());

        //관계식
        System.out.println(BigInteger.TWO.pow(N).subtract(BigInteger.ONE));

        // N이 20 이하일 경우 과정 출력
        if (N <= 20) {
            hanoi(N, 1, 2, 3);
        }

        bw.flush();
        bw.close();
        br.close();
    }

    // [로직] n 옮길 원판, from 시작 기둥, tmp 거쳐갈 기둥, to 도착 기둥
    public static void hanoi(int n, int from, int tmp, int to) throws IOException{

        // n == 1 일경우 바로 이동
        if (n == 1) {
            bw.write(from + " " + to + "\n"); // 이동
            return;
        }

        hanoi(n - 1, from, to, tmp);
        bw.write(from + " " + to + "\n"); // 이동

        hanoi(n-1, tmp, from, to);
    }
}

 

[시행착오]

 

그림판으로 그림까지 그려가며 하노이 탑을 공부하고 이해하려 노력했다. 코드는 다른글을 참고했지만 이해하기는했다.

처음엔 메모리초과가 발생했다. 알아본 결과 수가 너무 커질 경우 메모리 초과가 발생해 count 를 int 에서 long 으로 변경했다. 그런데 이번엔 시간초과가 발생했다. long 도 문제였다. 한 번 움직일 때마다 count 를 1씩 늘려주는 방식은 N이 매우 큰수가 될때 시간을 많이 잡아먹어 효율이 안좋았다. 애초에 시작할때 움직일만큼의 방정식을 계산해 출력을 해주는것이좋다. 그리고 그때의 타입은 BigInteger가 되어야만 했다. int, long 둘다 N이 100일 경우 메모리를 초과하기 때문이다.

N 이 20이상일 경우에는 hanoi() 자체가 실행되는순간 시간과 메모리를 많이 차지하기때문에 20 이하일 경우에만 hanoi()를 실행하게했다.

 

[정리]

원판의 개수 N을 입력받는다.

그 N을 이용해 관계식을 도출해 원판이 움직이는 횟수를 출력한다.

N이 20 이하일 경우 hanoi()를 실행한다.

 

[하노이 알고리즘]

 

그림과 hanoi() 를 같이 보면 이해하기 쉽다.

 

N개의 원판이 1번기둥에 있다. 제일 아래 큰 원판이 N 번째 원판이다.

hanoi(N, from, tmp, to) 실행

 

1단계 : N번째 원판을 옮기기 위해서는 N번째 원판을 제외한 N-1 번째부터 1번째 원판까지를 2번 기둥으로 옮긴다.

hanoi(N-1, from, to, tmp)

 

2단계 : N번째 원판을 3번 기둥으로 옮긴다.

이동

 

3단계 : N-1 번째부터 1번째 원판을 3번기둥으로 옮긴다.

hanoi(N-1, tmp, from, to)

 

이렇게 간단하게 3단계로 구성되어있다. 직접 알고리즘을 짜려면 어렵지만 막상 알고나면 생각보다 어렵지 않다.