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

헤메다 헤메다 결국 구글링을 통해 이해했다. 이 블로그에 하노이의 탑의 원리에 대해 굉장히 자세히 설명되어 있어 도움을 많이 받았다.

내가 놓친 부분이 재귀함수를 설계하는데 중요한 부분이였지 않나 싶다.
하노이의 탑에서 장대가 3개이므로 예를들어 A에서 C로 원판을 옮긴다고 하면, 무조건 다음 2가지 경우이다.

1. A에서 C로 바로 옮기기

2. A에서 B를 거쳐 C로 옮기기

따라서 이러한 점화식이 만들어진다. 원판이 하나밖에 없을때는 경유하는 장대 없이 바로 이동하게 하고,

아니라면
맨아래 원판만 빼고 모두 경유지로 옮긴다.
그리고 맨아래에 있던 원판을 목적지로 옮긴다.
마지막으로 경유지에 있던 나머지 원판들을 목적지로 옮긴다.

이 과정에서 hanoi함수가 재귀적으로 호출이 된다.

import java.util.*;
import java.io.*;


public class No11729_하노이탑이동순서 {
    static int cnt=0;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        hanoi(n,1, 3,2);
        System.out.println(cnt);

        System.out.print(sb.toString());
    }

    static void move(int n, int start, int to) {
        sb.append(start+" "+to+'\n');
        cnt++;
    }

    static void hanoi (int n, int start, int to, int via) {
        if (n==1) {
            move(1, start, to);
        }
        else {
            hanoi(n-1,start, via, to);
            move(n,start,to);
            hanoi(n-1,via,to,start);
        }
    }
}

설명하기가 굉장히 어려운것 같다...
경유지를 어떤식으로 들리는지 아는게 포인트가 아닐까(내가 헤맸던 부분)