하노이탑

 

재귀함수로 푼 하노이탑이다.

 

재귀함수는 종료조건과 문제정의를 잘해야한다.

 

종료조건은 블럭이 하나 남았을때 첫번째 기둥에서 마지막 기둥으로 옮기는것 이다.

 

문제정의

1.N개의 원반을 3번째(가정)으로 옮기기 위해서는 N-1개의 원반을 가운데로 이동을 해야함

2.N번째 원반을 3번째(가정)으로 이동시켜야 한다.

3.그리고 가운데에 있던 N-1개의 원반을 3번째(가정)으로 이동시켜야 한다. 

 

문제를 알고 읽는것이 일단 가장 중요하다.

 

public class Practice5 {
    static StringBuffer stringBuffer;

    public static void solution(int n) {
        stringBuffer = new StringBuffer();
        recursion(3,1,2,3);
        System.out.println(stringBuffer);
    }

    public static void recursion(int n, int start, int mid, int to){
        if(n == 1){ // 종료 조건 원반이 하나 남았으면 start에서 목적지로 옮기고 끝내라
            stringBuffer.append(start + " " + to + " \n");
            return;
        }

        recursion(n-1, start, to, mid); // start에 있는 n-1개 를 mid 중간에 옮겨라
        stringBuffer.append(start + " " + to + " \n"); // n번째 블럭을 마지막으로 옮겨라
        recursion(n-1, mid, start, to);// mid에 있는 n-1개를 마지막으로 옮겨라

    }

    public static void main(String[] args) {
        // Test code
        solution(2);
        System.out.println();

        solution(3);
        System.out.println();

        solution(4);
    }
}