[백준][JAVA]하노이 탑 이동 순서(11729번) - 재귀 algorithm

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

11729번: 하노이 탑 이동 순서

* 문제는 해당 게시물 참고바랍니다.

 

해당 문제는 재귀를 사용하여 동작을 구현하는 문제입니다.

 

method 내부에서 method 자신을 다시 호출하는 것을 '재귀호출(recursive call)'이라 합니다.

호출된 method는 '값에 의한 호출(call by value)'를 통해 원래의 값이 아닌 복사된 값으로 작업하기 때문에

호출한 method와는 관계없이 독립적인 작업수행을 합니다.

 

* 무한 반복에서 빠져나오기 위해서 재귀호출에는 조건문을 필수적으로 사용합니다.

 

이제 해당 문제를 해결한 코드에 대해 설명하겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;


public class Main {

    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        int start = 1;
        int end = 3;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        double try_num = Math.pow(2,n)-1;

        sb.append((int)try_num + "\n");
        hanoi(n,start,end);
        System.out.println(sb);

    }
    static void hanoi(int n, int start, int end){
        if(n==0){
            return;
        } else {
            hanoi(n-1, start, 6-start-end);
            sb.append(start + " " + end + "\n");
            hanoi(n-1, 6-start-end, end);
        }
    }


}

이번에는 입출력 방식을 다르게 사용해봤습니다.

계속 시간초과가 나왔기 때문에 시간을 줄일 방법을 연구하다가 

자바의 경우는 출력함수인 System.out.println()을 반복적으로 호출하면 성능이 매우 떨어진다는 사실을 알고

static StringBuilder sb = new StringBuilder();

StringBuilder를 사용하여 성능이 좋은 StringBuilder를 사용하였습니다.

 

또한 백준에서 자바의 Scanner 는 한 번만 입력받더라도 기본 수행시간이 100ms 를 넘어갈 정도로 효율이 좋지 않다는 사실을 알고

이번에 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());

BufferedReader로 buffer를 이용하여 입력의 효율을 높였습니다.

BufferedReader의 readLine()을 사용하면 데이터를 라인단위로 읽을 수 있습니다.

 

마지막으로

static void hanoi(int n, int start, int end){
    if(n==0){
        return;
    } else {
        hanoi(n-1, start, 6-start-end);
        sb.append(start + " " + end + "\n");
        hanoi(n-1, 6-start-end, end);
    }
}

해당 method에는 접근제어자를 사용하지 않았는데

접근제어자를 붙이지 않으면 default로 자동 적용되고 default는 어차피 같은 package 내에서 접근이 가능하므로 안붙였습니다.