하노이의 탑(Tower of Hanoi) 재귀 호출 구현하기

자료구조 책을 공부하다가 재귀함수파트가 너무 어려워서 이해한것을 잊어버릴까봐 글로 남긴다.
책대로 해야하는 것은 알겠는데 실제로 정말 될까를 이해하는 과정이 너무 힘들었다.
재귀 함수 안에 재귀함수가 2개이상 호출되는 경우 머리로 순서가 연산이 잘 안된다.ㅋㅋ

지금 생각해보니 몇시간동안 너무 어렵게 생각한 것 같다.
공부한 김에 정리하고 나중에 추가로 수정을 해야할 것이다.

이 코드에서 계속 잘못 생각하고 있었던 부분은 move 메소드 자체였는데,
move 메소드에서 x, y가 의미하는 바는 x 기둥에서 y기둥으로 옮긴다는 것이다.

어쨌든 이 코드에서의 큰 줄기는 가장 아래 원반을 제외한 나머지 원반그룹들을 두번째 기둥으로 옮긴 후 아래 원반을 세번째 기둥에 옮긴다.
그리고 원반 그룹들을 세번째에 옮기면 된다.

큰원반은 작은원반 위로 올라가질 못한다.
원반을 옮기려면 최소한 가장 작은 원반부터 건드려야 한다.

결국 move 메소드는 n개의 원반을 x 기둥에서 y기둥으로 옮긴다.
요약하면 아래와 같다.
기둥 번호는 차례대로 1,2,3 이다.

1. 위에서부터 n-1개의 원반들을 1번째 기둥에서 2번째 기둥으로 옮긴다. (1 -> 2)
2. 맨 아래의 원반 1개를 3번째 기둥으로 옮긴다 (1 -> 3)
3. 2번째 기둥에 있던 n-1개의 원반들을 3번째 기둥으로 옮긴다. (2 -> 3)

그런데 n-1개의 원반들을 기둥에서 기둥으로 옮길 때 move 메소드를 또다시 호출하게 된다. 다만 x, y인자를 어떤기둥에서 옮겨지는지 제대로 넣어주어야 한다.

그리고 원반 개수가 1이 될 때 실제로 옮겼다고 텍스트를 출력하게 된다.

public class Hanoi {
    /**
     * n개의 원반을 x 기둥에서 y 기둥으로 옮김
     * @param no 원반 개수
     * @param x 시작 기둥
     * @param y 목표 기둥
     */
    static void move(int no, int x, int y) {
        //가장 아래의 원반을 뺀 윗 그룹의 원반들을
        //처음 기둥에서 중간 기둥으로 이동한다.
        //x,y가 1과 3일때 6-x-y는 중간 기둥 값이다.
        //그리고 가장 마지막 기둥을 세번째 기둥으로 옮긴다.
        if (no > 1)
            move(no - 1, x, 6 - x - y);
        
        //실제 옮겼다고 출력하는 부분
        System.out.println("원반[" + no + "]을 " + x + "기둥에서 " + y + "기둥으로 옮김");

        //그룹 원반들(no-1)을 중간 기둥에서 목표 기둥으로 이동한다.
        if (no > 1)
            move(no - 1, 6 - x - y, y);
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        System.out.println("하노이의 탑");
        System.out.println("원반 개수:");
        int n = s.nextInt();

        //기둥 번호를 순서대로 1,2,3 칭함
        //하노이탑의 목표: n개의 원반을 1번 기둥에서 3번 기둥으로 옮김
        move(n, 1, 3);
    }
}