❤️‍🔥[자료구조 with Java]하노이탑 + 백준_11729

드디어 실버리그로 올라와서 자료구조를 같이 공부하면서 백준 문제를 풀기로 했다!

자료구조 개념 - 재귀

하노이탑

실제 움직이는 원리를 보면 다음과 같다.

참고

• https://st-lab.tistory.com/96
• https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91

---

관련 백준 문제

문제

접근 방법

• 하노이탑 알고리즘을 이용해서 문제를 해결한다.

import java.io.*;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static double hanoiMove(int n){
        return Math.pow(2,n)-1;
    }

    public static void hanoi(int n, int start, int mid, int to) throws IOException{

        if(n == 1){
            bw.write(start + " " + to + "\n");
            return; //옮길 원반이 하나
        }
        hanoi(n-1, start,to,mid);
        bw.write(start + " " + to + "\n");
        hanoi(n-1, mid,start,to);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int ans = (int) hanoiMove(n);
        bw.write(ans + "\n");
        hanoi(n, 1, 2, 3); //start, to, mid 번호

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

❌주의!
BufferedWriter의 flush를 사용해 한 번에 버퍼를 비워주는 방식으로 출력해야 시간초과가 안 생긴다. 해보니 print의 경우 StringBuilder를 사용하지 않으면 시간초과가 나더라

---

✅ 결과