[Algorithm/Java][백준] 11729 하노이 탑 이동 순서

[BOJ] 11729 하노이탑 이동 순서

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

문제 접근

일단 하노이 탑을 1에서 2를 거쳐서(이용해서?) 3으로 옮겨야 한다.
나의 직관적인? 접근 방식은 n이 3개일 때,
1.첫 함수 호출로 1 -> 3으로 가장 작은 것을 옮긴다.
2.그리고 다시 함수 호출로 1 -> 2로 두번째로 작은 것을 옮긴다. (이러면 가장 큰것이 1에 있다!)
3.이때는 함수 호출 하지 않고 1 -> 3으로 옮긴다. (이 때 3에 있는 가장 큰 것은 이제 없다고 생각해도 된다!)
4.이제 이 문제는 2개의 원반을 가진 하노이탑을 2 -> 3으로 옮기는 문제로 작아진다. => 함수 호출로 2->3으로 다시 작은 것을 옮긴다.

이 접근을 재귀적으로 잘 정리하면 이렇게 된다.
1.1 -> 3으로 n개를 옮기기 위한 함수를 호출 한다.
2.1 -> 2로 n-1개를 옮기기 위한 함수를 호출 한다.
3.1 -> 3으로 가장 큰 원반을 옮긴다.
4.2->3 으로 n-1개의 원반을 옮기기 위한 함수를 호출한다.

Code

import java.util.Scanner;

public class BOJ11729 {
    static int cnt = 0;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        hanoi(n,1,3,2);
        System.out.println(cnt);
        System.out.println(sb);
    }
    public static void hanoi(int n, int from, int to, int by){
        if(n == 1){
            move(from, to);
        } else {
            hanoi(n-1,from,by,to);
            move(from,to);
            hanoi(n-1,by,to,from);
        }
    }
    private static void move(int from, int to) {
        sb.append(from + " " + to+"\n");
        cnt++;
    }
}

어려웠던 점 / 배운 점 / 느낀 점

예전에 하노이 탑을 접했을 때는 되게 어려웠는데, 학년이 올라가서 그런가 이해가 잘 되는느낌이다!