백준 11729번 java 하노이 탑 이동 순서 [재귀]

하노이 탑 재귀 문제에서도 뭔가 이해가 잘 안되고 어렵다.

<시간 초과 코드>

import java.util.Scanner;
 
public class Main{
    //baekjoon 11729번 하노이탑
    static void hanoiMove(int n, int from, int by, int to) {
        if(n == 1) {
            System.out.println(from + " " + to);
        } 
        else {
            hanoiMove(n-1, from, to, by);
            System.out.println(from + " " + to);
            hanoiMove(n-1, by, from, to);
        }
    }
    
    static void hanoiNum(int n) {
        int num = 1;
        while(true) {
            if(n == 1)
                break;
            num = num * 2 + 1;
            n--;
        }
        System.out.println(num);
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        hanoiNum(n);
        hanoiMove(n, 1, 2, 3);
    }    
}
 

16행 : hanoiNum() 몇번의 이동이 있는지 구하는 함수

5행 : hanoiMove() 원판의 이동 구하는 함수

 

java에서 이렇게 풀었더니 시간초과로 오답처리가 되었다.

그래서 Scanner() 와 System.out.println() 대신 BufferedReader()와 Writer()를 사용해 보았다.

<정답 코드>

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
//import java.util.Scanner;
 
public class Main{
    //baekjoon 11729번 하노이탑
    static StringBuilder sb;
    
    static void hanoiMove(int n, int from, int by, int to) {
        if(n==1) {
            sb.append(from + " " + to + "\n");
        } else {
            hanoiMove(n-1, from, to, by);
            sb.append(from + " " + to + "\n");
            hanoiMove(n-1, by, from, to);
        }
    }
    
    static void hanoiNum(int n) {
        int num = 1;
        while (true) {
            if (n ==1) 
                break;
            num = num * 2 + 1;
            n--;
        }
        sb.append(num + "\n");
    }
    
    public static void main(String[] args) throws IOException {
        //Scanner sc = new Scanner(System.in);
        //int n = sc.nextInt();
        sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        
        hanoiNum(n);
        hanoiMove(n, 1, 2, 3);
        
        br.close();
        bw.write(sb.toString());
        bw.flush();
        bw.close();    
    }    
}

이렇게 하니 풀리긴 한다.